zcmimi's blog
查看原题

点击跳转

\sum_{i=1}^A\sum_{j=1}^B [\gcd(i,j)=d] \\ =\sum_{i=1}^{\left \lfloor \frac Ad \right \rfloor}\sum_{j=1}^{\left \lfloor \frac Bd\right \rfloor} [\gcd(i,j)=1] \\ =\sum_{i=1}^{\left \lfloor \frac Ad \right \rfloor}\sum_{j=1}^{\left \lfloor \frac Bd\right \rfloor} \sum_{x|i,x|j}\mu(x) \\ =\sum_{x=1}^n\mu(x) \left \lfloor \frac A{dx} \right \rfloor \left \lfloor \frac B{dx}\right \rfloor

#include<bits/stdc++.h>
const int N=1000011;
int n,m,d,mu[N],pri[N],cnt=0;
bool b[N];
inline int min(int x,int y){return x<y?x:y;}
int main(){
    scanf("%d%d%d",&n,&m,&d);
    n/=d;m/=d;
    if(n>m)n^=m,m^=n,n^=m;
    mu[1]=1;
    for(int i=2;i<=n;++i){
        if(!b[i])pri[++cnt]=i,mu[i]=-1;
        for(int j=1;j<=cnt&&i*pri[j]<=n;++j){
            b[i*pri[j]]=1;
            if(i%pri[j])mu[i*pri[j]]=-mu[i];
            else break;
        }
    }
    for(int i=2;i<=n;++i)mu[i]+=mu[i-1];
    long long res=0;
    for(int l=1,r,i,j;l<=n;l=r+1){
        i=n/l,j=m/l;
        r=min(n/i,m/j);
        res+=1ll*(mu[r]-mu[l-1])*i*j;
    }
    printf("%lld\n",res);
}
LG 4450 双亲数
comment评论
Search
search