bzoj2005 [Noi2010]能量采集（Mobius反演，欧拉函数）

我们发现点(x,y)到原点的连线上有gcd(x,y)-1个点（不含始终点），所以我们要求的答案就是 ∑x=1n∑y=1m2∗(gcd(x,y)−1)+1 也就是 2∑x=1n∑y=1mgcd(x,y)−n∗m
而 ∑x=1n∑y=1mgcd(x,y) 可以容斥原理求 O(nlogn)
还可以Mobius反演求，化一下就是：
∑d=1n∑t|dμ(t)dt⌊n/d⌋⌊m/d⌋
而 ∑t|dμ(t)dt=ϕ(d)
所以就是求 ∑d=1nϕ(d)⌊n/d⌋⌊m/d⌋
复杂度 O(n+n√)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 100010
inline char gc(){
    static char buf[1<<16],*S,*T;
    if(S==T){T=(S=buf)+fread(buf,1,1<<16,stdin);if(S==T) return EOF;}
    return *S++;
}
inline int read(){
    int x=0,f=1;char ch=gc();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc();
    return x*f;
}
int n,m,prime[N/10],tot=0;ll phi[N],ans=0;
bool notprime[N];
inline void getphi(){
    notprime[1]=1;phi[1]=1;
    for(int i=2;i<=n;++i){
        if(!notprime[i]) prime[++tot]=i,phi[i]=i-1;
        for(int j=1;prime[j]*i<=n;++j){
            notprime[prime[j]*i]=1;
            if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}
            phi[i*prime[j]]=phi[i]*phi[prime[j]];
        }
    }for(int i=2;i<=n;++i) phi[i]+=phi[i-1];
}
int main(){
// freopen("a.in","r",stdin);
    n=read();m=read();if(n>m) swap(n,m);getphi();
    for(int i=1,last;i<=n;i=last+1){
        last=min(n/(n/i),m/(m/i));
        ans+=(phi[last]-phi[i-1])*(n/i)*(m/i);
    }printf("%lld\n",ans*2-(ll)n*m);
    return 0;
}