lg3327

链接:lg3327

题解

  • $ans=\sum_{i}^n{\sum_{j}^m{gcd(i,j)=p}}$
  • $ans=\sum_{d \in p}^{}{\sum_{i}^{\frac nd}{\sum_{j}^{\frac md}{\sum_{x|gcd(i,j)}^{}{\mu(x)}}}}$
  • $ans=\sum_{d \in p}^{}{\sum_{x}^{min(\frac nd,\frac md)}{\mu(x)[\frac n{dx}][\frac m{dx}]}}$
  • 换一个枚举项,枚举dx
  • $ans=\sum_{T}^{min(n,m)}{\sum_{x|T}^{}{\mu(\frac Tx)[\frac nT][\frac mT]}}$
  • $ans=\sum_{T}^{min(n,m)}{[\frac nT][\frac mT]\sum_{x|T}^{}{\mu(\frac Tx)}}$
  • 显然这里就可以O($\sqrt n$)做了
    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
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstdlib>
    #include<cstring>
    #include<algorithm>
    #define rep(i,x,y) for(register int i=x;i<=y;++i)
    #define repd(i,x,y) for(register int i=x;i>=y;--i)
    #define ll long long
    using namespace std;
    const int N=1e7+7;
    int n,m,p[N],cnt,vis[N],mu[N],g[N],T,l,r;
    ll ans,sum[N];
    void get_mu(int n){
    mu[1]=1;
    rep(i,2,n){
    if(!vis[i])mu[i]=-1,p[++cnt]=i;
    for(int j=1;j<=cnt&&i<=n/p[j];++j){
    vis[i*p[j]]=1;
    if(i%p[j]==0)break;
    mu[i*p[j]]-=mu[i];
    }
    }
    rep(j,1,cnt)for(int i=1;i<=n/p[j];++i)g[i*p[j]]+=mu[i];
    rep(i,1,n)sum[i]=sum[i-1]+(ll)g[i];
    }
    int main(){
    scanf("%d",&T);
    get_mu(N-7);
    while(~scanf("%d%d",&n,&m)){
    ans=0;l=1;

    int len=min(n,m);
    while(l<=len){
    r=min(n/(n/l),m/(m/l));
    ans+=(ll)(n/l)*(m/l)*(sum[r]-sum[l-1]);
    l=r+1;
    }
    printf("%lld\n",ans);
    }
    return 0;
    }