BZOJ 2818 Gcd 线性欧拉

题意:链接

方法:线性欧拉

解析:

首先列一下表达式

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

然后我们可以得到什么呢？

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

不妨令y>=x

则可以得到我们要的答案就是$\sum_{i=1}^{max(y/z)}phi(i)$

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

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

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

代码：

正常人做法1.1s

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 10000010
using 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 <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 10000010
using 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);
}