洛谷P2568 GCD

发表于 | 分类于
字数统计: 190 | 阅读时长 ≈ 1

对于一组，若有一个质数p，则
枚举所有的p，求所有，的解，用欧拉函数即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<cstdio>
#define LL long long
const int N=10000050;
bool used[N];
int n,phi[N],prime[N>>3],cnt=0;
LL ans=0,sum[N];
void work()
{
    phi[1]=1;
    for(int i=2;i<=n;i++)
    {
        if (!used[i]) prime[++cnt]=i,phi[i]=i-1;
        for(int j=1;j<=cnt;j++)
        {
            if (prime[j]*i>n) break;
            used[i*prime[j]]=1;
            phi[i*prime[j]]=phi[i]*(prime[j]-1);
            if (i%prime[j]==0) {phi[i*prime[j]]+=phi[i];break;}
        }
    }
}
int main()
{
    scanf("%d",&n);
    work();
    for(int i=1;i<=n;i++) 
        sum[i]=sum[i-1]+phi[i];
    for(int i=1;i<=cnt;i++)
        ans=ans+sum[n/prime[i]]*2-1;
    printf("%lld",ans);	
    return 0;
}