BZOJ2190 SDOI2008 仪仗队 gcd,欧拉函数

题意：求从左下角能看到的元素个数

引理：对点(x,y)，连线(0,0)-(x,y)，元素个数为gcd(x,y)-1（中间元素）

即要求gcd(x,y)=1

求gcd(x,y)=1的个数

转化为2 \sum_(i=1)^(n-1) \phi(i) - 1 （思考如何转化）

感性分析，理性计算

 #include <bits/stdc++.h>

 using namespace std;

 int n,phi[];

 int main(){

     cin>>n;

     phi[]=;

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

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

         if(phi[i]==i)

             for(int j=i;j<=n;j+=i)

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

     long long ans=;

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

     if(n==) cout<<;

     else cout<<*ans+<<endl;

     return ;

 }

巴特西

BZOJ2190 SDOI2008 仪仗队 gcd,欧拉函数

最新文章

热门文章