题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2190
离线版题目:http://paste.ubuntu.com/20271981/
这个是“能量采集”的弱化版,所以mu和phi都可以很简单做
线筛写错了,wa了好久QAQ
#include<iostream> #include<cstdio> #include<bitset> using namespace std; const int MAXN = 40000+9; int n,pri[MAXN],tot,phi[MAXN]; bitset<MAXN> tag; inline void Get_Phi(){ phi[1] = 1; for (int i=2;i<=n;i++){ if (!tag[i]) pri[++tot] = i, phi[i] = i-1; for (int j=1;j<=tot && pri[j]*i<=n;j++) { tag[i*pri[j]] = 1; if (i % pri[j]) phi[i*pri[j]] = phi[i]*(pri[j]-1); else {phi[i*pri[j]] = phi[i]*pri[j]; break;} } } for (int i=2;i<=n;i++) phi[i] += phi[i-1]; } int main(){ scanf("%d",&n); n-=1; Get_Phi(); printf("%d\n",phi[n]*2-1+2); return 0; }
This is really interesting, You are a very skilled blogger. I have joined your rss feed and look forward to seeking more of your great post. Also, I have shared your site in my social networks!