原题链接
思路:
首先,显然当 为质数时, 是质数.
同时,若 且 时,有 且
此时答案已经呼之欲出了:从 入手,
计算出 即可知有多少 满足 , 然后计算出 内有多少质数,
再把两数相乘,即得到满足 且 为质数的数对数量了.
而这两个数可以通过线性筛在 的时间内预处理得到。问题便解决了.
代码:
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 <vector> using namespace std; const int Mn(10000500);
int phi[Mn],lsp[Mn]; vector<int> prm; void euler_sieve(int n) { phi[1] = 0; lsp[1] = 0; for(int i(2);i<=n;++i) { lsp[i] = lsp[i-1]; if(!phi[i]) { phi[i] = i-1; prm.push_back(i); ++lsp[i]; } for(int j(0);j<prm.size() && 1ll*i*prm[j]<=n;++j) { if(i%prm[j]==0) { phi[i*prm[j]] = phi[i]*prm[j]; break; } else { phi[i*prm[j]] = phi[i]*(prm[j]-1); } } } }
int main() { int n; scanf("%d",&n); euler_sieve(n); long long ans(0); for(int i(2);i<=n;++i) { if(phi[i]==i-1) { ans += 1; } ans += 2*phi[i]*lsp[n/i]; } printf("%lld",ans); return 0; }
|
Gitalking ...