题目大意
给定 n,求
i=1∑nφ(i)
1⩽n⩽2,000,000,000
题目链接
BZOJ 4805
题解
杜教筛模版题。
狄利克雷卷积有 φ×1=id,则有:
Φ(n)=2n(n+1)−i=2∑nΦ(⌊in⌋)
预处理出前 n32 项,复杂度为 O(n32)。
代码
把 < MAXNN
写成了 <= MAXNN
,RE了四次。。。
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 44
| #include <cstdio> #include <map> const int MAXNN = 1600000; long long phi[MAXNN]; int prime[MAXNN], primeCnt; bool notPrime[MAXNN]; void linearShaker() { phi[1] = 1; notPrime[0] = notPrime[1] = true; for (int i = 2; i < MAXNN; i++) { if (!notPrime[i]) { prime[++primeCnt] = i; phi[i] = i - 1; } for (int j = 1; j <= primeCnt && i * prime[j] < MAXNN; j++) { notPrime[i * prime[j]] = true; if (i % prime[j] == 0) { phi[i * prime[j]] = phi[i] * prime[j]; break; } else phi[i * prime[j]] = phi[i] * (prime[j] - 1); } } for (int i = 2; i < MAXNN; i++) phi[i] += phi[i - 1]; } long long pSumPhi(int n) { if (n < MAXNN) return ::phi[n]; static std::map<int, long long> phi; std::map<int, long long>::iterator it; if ((it = phi.find(n)) != phi.end()) return it->second; long long res = (long long) n * (n + 1) / 2; int last; for (int i = 2; i <= n; i = last + 1) { last = n / (n / i); res -= (last - i + 1) * pSumPhi(n / i); } return phi[n] = res; } int main() { int n; scanf("%d", &n); linearShaker(); printf("%lld\n", pSumPhi(n)); return 0; }
|