HDU 4834 JZP Set(数论+递推)(2014年百度之星程序设计大赛 - 初赛(第二轮))

时间:2023-03-08 16:39:47
Problem Description
一个{1, ..., n}的子集S被称为JZP集,当且仅当对于任意S中的两个数x,y,若(x+y)/2为整数,那么(x+y)/2也属于S。
例如,n=3,S={1,3}不是JZP集,因为(1+3)/2=2不属于S。但是{1,2,3}的其他子集都属于S,所以n=3时有7个JZP集
给定n,求JZP集的个数。
Input
第一行为T,表示输入数据组数。
每组数据包含一行整数n。

限制条件
1<=T<=10^5
1<=n<=10^7

Output
对第i组数据,输出
Case #i:
然后输出JZP集的个数。
题目大意:略。
思路:考虑到n高达10^7,而T也不小,选择递推预处理出所有答案。
观察(x+y)/2,对集合里的每个数都有这种规律的话,能想到类似的东西就是等差数列。
令ans[i]代表集合[1..i]的JZP子集(空集也算的),那么有ans[i] = ans[i - 1] + count(包含i的[1..i]的JZP子集)。
那么令p[i] = 包含i的[1..i]的JZP子集个数。考虑包含i的等差数列,可以发现等差一定为奇数(偶数都无法构成JZP集合,手动试一下就能发现了)。
首先p[i]有只包含一个数的{i}。
之后对于元素个数大于等于2的,等差为1的子集个数为(i-1)/1,等差为3的子集个数为(i-1)/3……
但是这还不能满足题目的要求。
考虑p[i]-1和p[i-1]-1的区别,对于(i-1)/1+(i-1)/3+(i-1)/5……和(i-2)/1+(i-2)/3+(i-2)/5……,对于分母为x的,(i-1) / x > (i-2) / x当且仅当(i-1)是x的倍数
可以得出p[i]比p[i-1]要大count(i-1的奇数约数)。
对于每个数的约数个数,可以在O(nlogn)的时间里预处理出来(参考素数的筛法)。
然后递推ans[i] = ans[i - 1] + p[i],至此题目完美解决!
代码(2109MS):
 #include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
typedef long long LL; const int MAXN = 1e7 + ; int cnt[MAXN];
LL ans[MAXN]; void initc() {
int n = 1e7;
for(int i = ; i <= n; i += ) {
for(int j = i; j <= n; j += i) cnt[j]++;
}
} void init() {
initc();
int n = 1e7;
ans[] = ;
LL t = ;
for(int i = ; i <= n; ++i) {
t += cnt[i - ];
ans[i] = ans[i - ] + t + ;
}
} int main() {
init();
int T, n;
scanf("%d", &T);
for(int t = ; t <= T; ++t) {
scanf("%d", &n);
printf("Case #%d:\n", t);
printf("%I64d\n", ans[n]);
}
}