BZOJ 2818 Gcd 线性欧拉-白红宇

BZOJ 2818 Gcd 线性欧拉

阅读量：5085 次

发布时间：2019-06-13

本文共 2436 字，大约阅读时间需要 8 分钟。

题意:

方法:线性欧拉

解析:

首先列一下表达式

gcd(x,y)=z(z是素数而且x,y<=n).

然后我们能够得到什么呢？

gcd(x/z,y/z)=1;

最好还是令y>=x

则能够得到我们要的答案就是∑max(y/z)i=1phi(i)

而max(y/z)就是max(n/z)。

所以仅仅须要枚举一下质数z随便搞一下就好了，最好用前缀和记录

HINT：前缀和写树状数组的都是(*)

代码：

正常人做法1.1s

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #define N 10000010using namespace std;typedef long long ll;int n,tot;int prime[N];int phi[N];ll sum[N];int f[N];void sieve(){    phi[1]=1;    sum[1]=1;    for(int i=2;i<=n;i++)    {        if(!f[i])        {            prime[++tot]=i;            phi[i]=i-1;        }        for(int j=1;j<=tot,i*prime[j]<=n;j++)        {            f[i*prime[j]]=1;            if(i%prime[j]==0)            {                phi[i*prime[j]]=phi[i]*prime[j];                break;            }else            {                phi[i*prime[j]]=phi[i]*phi[prime[j]];            }        }        sum[i]=sum[i-1]+phi[i];    }}int main(){    scanf("%d",&n);    sieve();    ll print=0;    for(int i=1;i<=tot;i++)    {        int up=n/prime[i];        print+=sum[up];    }    printf("%lld\n",print*2-tot);}

树状数组4.8s

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #define N 10000010using namespace std;typedef long long ll;int n,tot;int prime[N];int phi[N];ll sum[N];int f[N];int lowbit(int x){
     return x&(-x);}void update(int x,int p){    while(x<=n)    {        sum[x]+=p;        x+=lowbit(x);    }}ll getsum(int x){    ll ret=0;    while(x)    {        ret+=sum[x];        x-=lowbit(x);    }    return ret;}void sieve(){    phi[1]=1;    update(1,1);    for(int i=2;i<=n;i++)    {        if(!f[i])        {            prime[++tot]=i;            phi[i]=i-1;            update(i,phi[i]);        }        for(int j=1;j<=tot,i*prime[j]<=n;j++)        {            f[i*prime[j]]=1;            if(i%prime[j]==0)            {                phi[i*prime[j]]=phi[i]*prime[j];                update(i*prime[j],phi[i*prime[j]]);                break;            }else            {                phi[i*prime[j]]=phi[i]*phi[prime[j]];                update(i*prime[j],phi[i*prime[j]]);            }        }    }}int main(){    scanf("%d",&n);    sieve();    ll print=0;    for(int i=1;i<=tot;i++)    {        int up=n/prime[i];        print+=getsum(up);    }    printf("%lld\n",print*2-tot);}