【数论】【筛法求素数】【欧拉函数】bzoj2818 Gcd

gcd(x,y)(1<=x,y<=n)为素数(暂且把(x,y)和(y,x)算一种) 的个数

<=> gcd(x/k,y/k)=1，k是x的质因数的个数

<=> Σφ(x/k) (1<=x<=n,k是x的质因子)

这样的复杂度无法接受，

∴我们可以考虑枚举k，计算Σφ(q/k) (k是n以内的质数，q是n以内k的倍数)，即Σ[φ(1)+φ(2)+φ(3)+...+φ(p)] (p=n/k)

介个phi的前缀和可以预处理粗来。

但是(x,y)和(y,x)并不同，所以在计算前缀和的时候，对于φ(x) (x≠1)，要乘2再累加，即Σ[φ(1)+φ(2)*2+φ(3)*2+...+φ(p)*2] (p=n/k)。

∴对每个n以内的素数，我们可以O(1)地得到其对答案的贡献。

∴时间复杂度花费在筛素数和预处理phi上，为O(n*log(log(n)))或O(n)[线性筛]。

 #include<cstdio>

 using namespace std;

 typedef long long ll;

 int phi[],n;

 bool unPrime[];

 ll ans,sum[];

 void Shai_Prime()

 {

     unPrime[]=;

     for(ll i=;i<=n;i++) if(!unPrime[i])

       {

           ans+=sum[n/i];

           for(ll j=i*i;j<=n;j+=i)

           unPrime[j]=;

       }

 }

 void phi_table()

 {

     phi[]=;//规定phi(1)=1;

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

       if(!phi[i])//若i是质数(类似筛法的思想)

         for(int j=i;j<=n;j+=i)//i一定是j的质因数

           {

             if(!phi[j]) phi[j]=j;

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

           }

 }

 void init_sum()

 {

     sum[]=phi[];

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

 }

 int main()

 {

     scanf("%d",&n); phi_table(); init_sum(); Shai_Prime();

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

     return ;

 }

巴特西

【数论】【筛法求素数】【欧拉函数】bzoj2818 Gcd

最新文章

热门文章