1. 题目

biubiu

2. 题解

ans=$sigma((gcd(x,y)-1)×2+1)$（1<=x<=n,1<=y<=m）

设 f[d] 为 gcd(x,y)==d 的 x，y 对数

g[d] 为 gcd(x,y)%d==0 的 x，y 对数

g[d]=sigma(f[n]) d|n 由莫比乌斯反演

f[d]=sigma(u[n/d]×g[n]) d|n

g[u] 是很好求的 g[u]=n/u×m/u

那么 $ans=f[i]×((i-1)×2+1)$

代码：

#include<bits/stdc++.h>
const int MN=100000+10;
using namespace std;
int vis[MN],pri[MN],miu[MN],cnt;
int n,m;
long long ans,f[MN],g[MN];
void make(int size){
    miu[1]=1;
    for(int i=2;i<=n;++i){
        if(!vis[i])pri[++cnt]=i,miu[i]=-1;
        for(int j=1;j<=cnt&&pri[j]*i<=size;++j){
            vis[i*pri[j]]=1;
            if(i%pri[j]==0){
                miu[i*pri[j]]=0;
                break;
            }
            miu[i*pri[j]]=-miu[i];  
        }   
    }
}
int main(){
    freopen("a.in","r",stdin);
    scanf("%d%d",&n,&m);make(max(n,m));
    for(int i=1;i<=min(n,m);++i)
        g[i]=((long long)n/i)*((long long)m/i);
    for(int i=1;i<=min(n,m);++i){
        for(int j=1;j*i<=min(n,m);++j)
            f[i]+=miu[j]*g[i*j];    
    }
    for(int i=1;i<=min(n,m);++i)
        ans+=f[i]*(i*2-1);
    printf("%lld",ans);
    return 0;
}