题目链接
SPOJ-APS2
思路
用min_25筛的思路，也就是埃筛的思想，维护一个前缀和和一个个数数组，
然后枚举质数来判断合数的贡献。
例如 N=17时，枚举质数2，然后分块的思想，找出17/2所在的块的大小，也就是8
然后2~ 8这个区间乘上2的话也在1~17之中，所以贡献就多了8-(2-1)*2,然后不断枚举下去。
合数部分就解决了，然后我们解决质数部分，就用min_25筛就好了。
最后的g[id]表示区间素数和，然后ans就是我们计算的合数部分了
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include<cstdio>
#include<algorithm>
#include<ctype.h>
#include<string.h>
#include<math.h>
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 1111115;
int T, id, sn, cnt, prime[N];
ll n, a[N<<1];
ull g[N<<1], h[N<<1];
bool p[N];
inline int Id(ll x){ return x<=sn?x:id-n/x+1;}
int main() {
scanf("%d", &T);
while(T--){
scanf("%lld", &n), sn=sqrt(n);
cnt=id=0;
for(ll i=1; i<=n; i=a[id]+1)
a[++id]=n/(n/i), g[id]=(a[id]&1?(a[id]+1)/2*a[id]:(ull)a[id]/2*(a[id]+1))-1, h[id]=a[id]-1;
ull ans=0;
for(int i=2; i<=sn; ++i) if(h[i]!=h[i-1]){
prime[++cnt]=i;
ll lim=(ll)i*i;
for(int j=id, t; a[j]>=lim; --j){
g[j]-=i*(g[t=Id(a[j]/i)]-g[i-1]),h[j]-=h[t]-h[i-1];
if(j==id) ans+=(h[t]-h[i-1])*i;
}
}
printf("%llu\n", ans+g[id]);
}
return 0;
}
|