题解 P1390 【公约数的和】

青衫白叙 · 2017-10-21 14:22:29 · 题解

其实这题和P2389差不多还简单一些

这里介绍一种O( n )的做法

直接上图:

然后ans=(cal(n,n)-n*(n+1)/2)/2 减去gcd(d,d)=d的和gcd(i,j)=gcd(j,i)重复的

（恩，楼下的dalao我们好巧）。。不知道为什么 int 会WA。。全long long 就A了。。

上代码吧。。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=2e6+5;
ll p[N],n;ll phi[N];bool notp[N];
void seive(ll n){
    phi[1] = 1;
    for(ll i=2;i<=n;++i) {
        if(!notp[i]) p[++p[0]] = i, phi[i] = i-1;
        for(ll j=1;j<=p[0] && i*p[j]<=n;++j) {
            notp[i*p[j]] = 1;
            if(i%p[j]==0){phi[i*p[j]]=phi[i]*p[j];break;}
            phi[i*p[j]] = phi[i]*(p[j]-1);
        }
    }
    for(ll i=1;i<=n;++i) phi[i] += phi[i-1];
}
ll cal(ll n,ll m){
    ll ans = 0;ll r;
    for(ll i=1;i<=n;i=r+1) {
        r = min(n/(n/i), m/(m/i));
        ans += (phi[r]-phi[i-1]) * (n/i) * (m/i);
    }
    return ans;
}
int main() {
    scanf("%lld",&n);
    seive(n);
    printf("%lld\n",(cal(n,n)-n*(n+1)/2)/2);
}