[BZOJ2190][SDOI2008]仪仗队 数学

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2190

看到这道题首先想到了NOI2010的能量采集，这不就是赤裸裸的弱化版吗？直接上莫比乌斯反演就行了。

令$f(d)=\sum_{i=1}^n\sum_{j=1}^n[gcd(i,j)==d]$

则有$g(d)=\sum_{i=1}^n\sum_{j=1}^n[d|gcd(i,j)]=\frac{n}{d}\frac{n}{d}=\sum_{d|n}f(d)$

由莫比乌斯反演得$f(d)=\sum_{d|n}μ(\frac{n}{d})F(n)=\sum_{x=1}^nμ(x)\frac{n}{dx}\frac{n}{dx}$

然而并没有写，因为发现有更简单的做法。

其实我们发现除开对角线单看一半，就是求小于n的x的phi值的和是多少，根据$gcd(a,b)=1$容易观察出来，然后最后加上对角线还有x轴y轴上三个特殊的点就可以了。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 int p[],cnt=;

 int phi[];

 bool vis[];

 void sieve(){

     for(int i=;i<=;i++){

         if(!vis[i]){

             p[++cnt]=i;

             phi[i]=i-;

         }

         for(int j=;p[j]*i<=&&j<=cnt;j++){

             vis[i*p[j]]=true;

             if(i%p[j]==){

                 phi[i*p[j]]=phi[i]*p[j];

                 break;

             }

             phi[i*p[j]]=phi[i]*(p[j]-);

         }

     }

 }

 int N;

 int main(){

     sieve();

     scanf("%d",&N);

     ll ans=;

     for(int i=;i<N;i++) ans+=phi[i];

     ans=ans*+;

     printf("%lld\n",ans);

     return ;

 }