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; } C++Copy 分类: 文章 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 下午 这题还有另外的解法的 发表回复 取消回复您的邮箱地址不会被公开。 必填项已用 * 标注 名称 * 电子邮件 * 网站 在想些什么? Δ
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 下午
这题还有另外的解法的