求 gcd(x,y)=p 等价于求 gcd(x/p,y/p)=1, 转化为了 n/p 内互质的个数
所以欧拉函数, 因为有序所以乘 2, 再特判一下只有在 1,1 情况下才会重复计算, 所以每次都减一
数组开小一时爽, 提交 wa 火葬场!!!
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- using namespace std;
- const int maxn=10000009;
- int n;
- int ck[maxn],prime[maxn],phi[maxn],tot;
- long long sum[maxn];
- void eular(int n){
- phi[1]=1;
- for(int i=2;i<=n;i++){
- if(!ck[i]){
- ck[i]=i,prime[++tot]=i;
- phi[i]=i-1;
- }
- for(int j=1;j<=tot;j++){
- if(prime[j]>ck[i] || i*prime[j]>n)break;
- ck[prime[j]*i]=prime[j];
- phi[i*prime[j]]=phi[i]*(i%prime[j]?prime[j]-1:prime[j]);
- }
- }
- }
- int main(){
- scanf("%d",&n);
- eular(n);
- for(int i=1;i<=n;i++)sum[i]=sum[i-1]+phi[i];
- long long ans=0;
- for(int i=1;i<=tot;i++){
- ans+=2*sum[n/prime[i]]-1;
- }
- printf("%lld\n",ans);
- }
[题解](gcd / 欧拉函数)luogu_P2568_GCD
来源: http://www.bubuko.com/infodetail-3059315.html