0%

「SPOJ APS2」Amazing Prime Sequence (hard)

SPOJ APS2

题意

令 $f(i)$ 表示 $i$ 的最小质因子

求 $$\sum_{i=2}^n f(i)$$

$n\le 1.234567891011*10^{12}$


做法

  • 对于质数 $p$,有 $f(p)=p$

  • 对于合数 $x$,有 $f(x)\le \sqrt{x}$

于是单独处理质数部分,然后枚举一个 $\le \sqrt{n}$ 的质数,计算贡献

Min_25筛,求质数的和只需要第一部分即可

复杂度 $\mathcal O(\frac{n^{\frac{3}{4}}}{\log n})$

考虑求合数的贡献

一种做法

令 $S(a,b)$ 表示 $[2,a]$ 中最小质因子 $\ge prime_b$ 的数的个数,其中 $prime_b$ 表示第 $b$ 个质数

那么合数的答案就是

$$\sum_{prime_i\le \sqrt{n}} S(\lfloor \frac{n}{prime_i} \rfloor, i) * prime_i$$

使用Min_25筛暴力求 $S$,可以通过此题

复杂度我不知道

另一种做法

令 $S(a,b)$ 表示 $[2,a]$ 中是质数或最小质因子 $\ge prime_b$ 的数的个数

这可以滚动第二维求,合数的答案是

$$\sum_{prime_i\le \sqrt{n}} \left( S(\lfloor \frac{n}{prime_i} \rfloor, i) - \left( i-1 \right) \right) * prime_i$$

要注意去掉质数的数量

在做的过程中计算即可

复杂度 $\mathcal O(\frac{n^{\frac{3}{4}}}{\log n})$

跑得没前一种方法快

又学会了另一种做法..

事实上这里不需要计算第二部分,由于只和最小质因子相关,第一部分里筛掉的数可以直接计算对答案的贡献

这样就肯定比前两种快了

具体可以看代码

代码

在SPOJ上总用时分别为 $31.13s,49.90s,19.83s$

第一种做法

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
37
38
39
40
41
42
43
#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;
ull g[N<<1], a[N<<1], h[N<<1];
bool p[N];
inline int Id(ll x){ return x<=sn?x:id-n/x+1;}
ull S(ll a, int b){
if(a<prime[b]) return 0;
ll ans=h[Id(a)]-(b-1);
for(int i=b; i<=cnt && (ll)prime[i]*prime[i]<=a; ++i){
ans+=S(a/prime[i], i+1)+1;
for(ll x=(ll)prime[i]*prime[i]; x*prime[i]<=a; x*=prime[i]) ans+=S(a/x, i+1)+1;
}
return ans;
}
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;
for(int i=2; i<=sn; ++i) if(h[i]!=h[i-1]){
prime[++cnt]=i;
ull lim=(ull)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];
}
ull ans=g[id];
for(int i=1; i<=cnt; ++i) ans+=S(n/prime[i], i)*prime[i];
printf("%llu\n", ans);
}
return 0;
}

第二种做法

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
37
38
39
40
#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], S[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;
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];
}
ull ans=g[id];
for(int i=1; i<=id; ++i) S[i]=h[i];
for(int i=cnt; i; --i){
for(int j=id; (ll)prime[i]*prime[i]<=a[j]; --j)
for(ll x=prime[i]; x*prime[i]<=a[j]; x*=prime[i])
S[j]+=S[Id(a[j]/x)]-i+1;
ans+=(S[Id(n/prime[i])]-i+1)*prime[i];
}
printf("%llu\n", ans);
}
return 0;
}

第三种代码

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;
}