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;
}
分类: 文章

6 条评论

boshi · 2017年7月10日 12:29 下午

%%%%%%%%

    tense · 2017年7月12日 10:48 上午

    大佬,发几发博客呗

      konnyakuxzy · 2017年7月12日 2:05 下午

      dalao 没有鸟你并且丢给你了一个 tan90°

        boshi · 2017年7月23日 2:24 下午

        然而真正的大佬出现了

konnyakuxzy · 2017年7月9日 10:22 下午

%%%%%%%Orz 太强啦%%%%%Orz

tense · 2017年7月9日 9:59 下午

这题还有另外的解法的

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注