题目链接:VJ(private)
Euler Sieve
题目描述
定义函数f为约数和函数和欧拉函数的卷积。求f前n项和。
1 <= n <= 5e6
解释
用欧拉筛(线性筛)筛素数的同时求出每项的欧拉函数和约数和函数。用双重循环将f的前n项和直接累加。
代码部分
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
| #include<bits/stdc++.h> using namespace std; int prime[5050000]; bool flag[5050000]; int phi[5050000]; int f[5050000]; int g[5050000]; int cnt; int main() { int n; cin>>n; flag[1]=true; phi[1]=f[1]=g[1]=1; for (int i=1;i<=n;i++) { if (!flag[i]) { prime[++cnt]=i; phi[i]=i-1; f[i]=i+1; g[i]=i+1; } for (int j=1;j<=cnt&&i*prime[j]<=n;j++) { flag[i*prime[j]]=true; if (i%prime[j]==0) { phi[i*prime[j]]=phi[i]*prime[j]; g[i*prime[j]]=g[i]*prime[j]+1; f[i*prime[j]]=f[i]/g[i]*g[i*prime[j]]; break; } phi[i*prime[j]]=phi[i]*(prime[j]-1); f[i*prime[j]]=f[i]*f[prime[j]]; g[i*prime[j]]=1+prime[j]; } } long long ans=0; for (int i=1;i<=n;i++) for (int j=1;j<=n/i;j++) ans+=phi[i]*f[j]; cout<<ans<<endl; return 0; }
|
补充
积性函数可以用欧拉筛来求出每一项值。常见的积性函数有欧拉函数、莫比乌斯函数、约数个数函数、约数和函数。
以下是oi-wiki中求四种积性函数的代码。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| void pre() { memset(is_prime, 1, sizeof(is_prime)); int cnt = 0; is_prime[1] = 0; phi[1] = 1; for (int i = 2; i <= 5000000; i++) { if (is_prime[i]) { prime[++cnt] = i; phi[i] = i - 1; } for (int j = 1; j <= cnt && i * prime[j] <= 5000000; j++) { is_prime[i * prime[j]] = 0; if (i % prime[j]) phi[i * prime[j]] = phi[i] * phi[prime[j]]; else { phi[i * prime[j]] = phi[i] * prime[j]; break; } } } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| void pre() { mu[1] = 1; for (int i = 2; i <= 1e7; ++i) { if (!v[i]) mu[i] = -1, p[++tot] = i; for (int j = 1; j <= tot && i <= 1e7 / p[j]; ++j) { v[i * p[j]] = 1; if (i % p[j] == 0) { mu[i * p[j]] = 0; break; } else { mu[i * p[j]] = -mu[i]; } } } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| void pre() { d[1] = 1; for (int i = 2; i <= n; ++i) { if (!v[i]) v[i] = 1, p[++tot] = i, d[i] = 2, num[i] = 1; for (int j = 1; j <= tot && i <= n / p[j]; ++j) { v[p[j] * i] = 1; if (i % p[j] == 0) { num[i * p[j]] = num[i] + 1; d[i * p[j]] = d[i] / num[i * p[j]] * (num[i * p[j]] + 1); break; } else { num[i * p[j]] = 1; d[i * p[j]] = d[i] * 2; } } } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| void pre() { g[1] = f[1] = 1; for (int i = 2; i <= n; ++i) { if (!v[i]) v[i] = 1, p[++tot] = i, g[i] = i + 1, f[i] = i + 1; for (int j = 1; j <= tot && i <= n / p[j]; ++j) { v[p[j] * i] = 1; if (i % p[j] == 0) { g[i * p[j]] = g[i] * p[j] + 1; f[i * p[j]] = f[i] / g[i] * g[i * p[j]]; break; } else { f[i * p[j]] = f[i] * f[p[j]]; g[i * p[j]] = 1 + p[j]; } } } }
|