题目链接

题目描述

设d(x)为x的约数个数，给定N,M,求∑Ni=1∑Mj=1d(ij) 设 d ( x ) 为 x 的 约 数 个 数 ， 给 定 N , M , 求 ∑ i = 1 N ∑ j = 1 M d ( i j ) $设d(x)为x的约数个数，给定N,M,求\sum^N_{i=1}\sum^M_{j=1}d(ij)$
其中d(x)表示x的约数个数 其 中 d ( x ) 表 示 x 的 约 数 个 数 $其中d(x)表示x的约数个数$

题解

首先要知道如下结论:
$d(ij)=\sum^i_{k|i}\sum^j_{l|j}gcd(k,l)=1$

然后开始随便推式子：
原式化为

$$\sum^N_{i=1}\sum^M_{j=1}\sum^i_{k|i}\sum^j_{l|j}gcd(k,l)=1$$

因为我们有$\sum_{d|n}\mu(d)=1\;\;\;(n=1)$

$$\sum^N_{i=1}\sum^M_{j=1}\sum^i_{k|i}\sum^j_{l|j}\sum_{d|gcd(k,l)}\mu(d)$$
对于每一个 $k,l$会被算到 N/k∗M/l次 N / k ∗ M / l 次 $N/k*M/l次$(可去掉最外层两个sigma)
$$\sum^N_k\sum^M_l\frac{N}{k}*\frac{M}{l}\sum_{d|gcd(k,l)}\mu(d)$$

枚举d

$$\sum^{min(N,M)}_{d=1}\mu(d)\sum^{\frac{N}{d}}_{k=1}\sum^{\frac{M}{d}}_{l=1}\frac{N}{kd}*\frac{M}{ld}$$
$$\sum^{min(N,M)}_{d=1}\mu(d)\sum^{\frac{N}{d}}_{k=1}\frac{N}{kd}\sum^{\frac{M}{d}}_{l=1}\frac{M}{ld}$$
令 $g(x)=\sum^n_{i=1}\frac{n}{i}$
则
$$\sum^{min(N,M)}_{d=1}\mu(d)*g(\frac{N}{d})*g(\frac{M}{d})$$

筛g不能想当然地递推，会WA，而要用筛的方法
其实简单想想就会发现g(n)是n内所有数的约数个数的和，可以分别筛出每个数的约数个数，然后再求前缀和。

约数个数是个积性函数，可以筛。

#include
#include
#include
#include
#include
#include
#include
using namespace std;
inline int read()
{int x=0;char ch=getchar();int t=1;for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') t=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch-48);return x*t;
}
int n,m;
const int N=5e4+100;
typedef long long ll;
int cnt=0;int pri[N];
int c[N];//某数的质因子的次数中的最小的次数
int mu[N];int g[N];bool vis[N];
inline void prepare()
{mu[1]=1;vis[1]=1;g[1]=c[1]=1;for(register int i=2;iif(!vis[i]) {mu[i]=-1;pri[++cnt]=i;g[i]=2;c[i]=1;}for(register int j=1;j<=cnt&&(1ll*pri[j]*iregister int x=pri[j]*i;vis[x]=1;if(i%pri[j]) {mu[x]=-mu[i];g[x]=g[i]*g[pri[j]];c[x]=1;}else {g[x]=g[i]/(c[i]+1)*(c[i]+2);c[x]=c[i]+1;mu[x]=0;break;}}}for(register int i=1;i1];for(register int i=2;i1];
}int main()
{int T=read();prepare();while(T--){n=read();m=read();if(n>m) swap(n,m);register int l=0,r=0;register ll ans=0;for(l=1;l<=n;l=r+1){r=min(n/(n/l),m/(m/l));if(r>n) r=n;ans+=1ll*(mu[r]-mu[l-1])*g[n/l]*g[m/l];}printf("%lld\n",ans);}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！