显然这题要求
$$\sum_{i\in [1,n]}\sum_{j\in [1,m]}gcd(i,j)$$
手推了半天不会做,感觉很复杂的容斥
一看题解发现真**巧妙
令\(f[k]\)表示\(gcd(i,j)=k\)的\((i,j)\)对数
那么首先满足\(k|gcd(i,j)\)的\((i,j)\)对数为\(\left\lfloor\frac{n}{k}\right\rfloor\times\left\lfloor\frac{m}{k}\right\rfloor\)
再减去整数倍的就可以了
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 |
#include <cstdio> #include <algorithm> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=100001; lol f[MAXN]; int main(){ int n=gi(),m=gi(); if(n>m)swap(n,m); lol ans=0; for(int i=n;i;i--){ f[i]=1ll*(n/i)*(m/i); for(int j=i<<1;j<=n;j+=i)f[i]-=f[j]; ans+=f[i]*((i<<1)-1); } printf("%lld",ans); return 0; } |
Update:学了莫比乌斯反演回来再把这题做一下(虽然还麻烦一些?)
令\(f(k)\)表示\(gcd(i,j)=k\)的\((i,j)\)对数,\(g(k)\)表示\(k|gcd(i,j)\)的\((i,j)\)对数
那么显然有\(g(k)=\sum_{k|d}f(d)=\left\lfloor\frac{n}{k}\right\rfloor\times\left\lfloor\frac{m}{k}\right\rfloor\)
用一下莫比乌斯反演\(f(k)=\sum_{k|d}\mu(\frac{d}{k})g(d)\)
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 |
#include <iostream> #include <algorithm> #include <cstdio> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=100001; bool np[MAXN]; int pc,pr[MAXN],mu[MAXN]; int main(){ int n=gi(),m=gi(); if(n>m)swap(n,m); mu[1]=1; for(int i=2;i<=n;i++){ if(!np[i]){pr[++pc]=i;mu[i]=-1;} for(int j=1;j<=pc&&i*pr[j]<=n;j++){ np[i*pr[j]]=1; if(i%pr[j])mu[i*pr[j]]=-mu[i]; else{mu[i*pr[j]]=0;break;} } } lol ans=0; for(int i=1;i<=n;i++) for(int j=1;i*j<=n;j++) ans+=1ll*mu[j]*(n/(i*j))*(m/(i*j))*((i<<1)-1); printf("%lld",ans); return 0; } |