[SDOI2015]约数个数和
题目描述
设d(x)为x的约数个数，给定N、M，求 \(\sum^N_{i=1}\sum^M_{j=1}d(ij)\)
输入输出格式
输入格式：
输入文件包含多组测试数据。第一行，一个整数T，表示测试数据的组数。接下来的T行，每行两个整数N、M。
输出格式：
T行，每行一个整数，表示你所求的答案。
输入输出样例
输入样例#1：
2
7 4 5 6输出样例#1：
110
121说明
\(1<=N, M<=50000\)
\(1<=T<=50000\)
Solution
莫比乌斯反演套路题
做这道题需要一个关于约数函数的公式
\[d(ij)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]\] 关于这个公式,先感性理解一下,可以理解成因为不能重复,所以gcd(x,y)=1,求这种数的总个数 下面是证明设ij的质因子p
左边\(i=ii\times p^a,j=jj\times p^b,ij=ii\times jj\times p^{a+b}\),后面的p有0~a+b共(a+b+1)种取值,即每个因子p对d(ij)有(a+b+1)的贡献 右边\((xx\times p^a,yy),(xx \times p^{a-1},yy)....(xx,yy)....(xx,yy\times p^{b-1}),(xx,yy\times p^{b})\),也是(a+b+1)个数对,故上式成立 因为\(gcd(x,y)=1\),所以两个因子之间是互不影响的
然后给我讲莫比乌斯反演的shenlao告诉我只需要记住下面这个公式,做题贼爽(好像是的)
\[[gcd(i,j)=1]=\sum_{d|gcd(i,j)}\mu(d)\] 一定要记住!!!(敲重点)现在式子变成了
\[Ans=\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}\sum_{d|gcd(x,y)}\mu(d)\] 更换枚举项,由枚举gcd(i,j)的约数改为直接枚举d\[Ans=\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}\sum_{d=1}^{min(n,m)}\mu(d)\times[d|gcd(x,y)]\]\(\mu(d)\)与\(i,j\)无关,提出来\[Ans=\sum_{d=1}^{min(n,m)}\mu(d)\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}[d|gcd(x,y)]\] 再次更换枚举项,由分别枚举i,j和及i,j的因子改为枚举i,j的因子,再直接乘上每个因子对它们产生的贡献\[Ans=\sum_{d=1}^{min(n,m)}\mu(d)\sum_{x=1}^n\sum_{y=1}^m[d|gcd(x,y)]\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor\] 继续更换枚举项,将枚举x,y换成枚举dx,dy,这样\([d|gcd(x,y)]\)这个条件就可以省去,因为保证了此时x=dx,y=dy,d一定是x,y的因子,那么枚举范围也要相应缩小\[Ans=\sum_{d=1}^{min(n,m)}\mu(d)\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor\]\(\lfloor\frac{n}{x}\rfloor\)对枚举y没有影响,提前就好了,所以最后答案就变成了\[Ans=\sum_{d=1}^{min(n,m)}\mu(d)\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{x}\rfloor\sum_{y=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{m}{y}\rfloor\] 因为多组询问,预处理之后\(O(\sqrt n)\)处理就可了 不会预处理的先去做一做这道题 怎么\(O(\sqrt n)\)优化?Code
#include#define il inline#define rg register#define lol long long#define NN 50000#define Min(a,b) (a)<(b)?(a):(b)#define Max(a,b) (a)?(b)?(a):(b)using namespace std;const int N=5e4+10;void in(int &ans) { ans=0; char i=getchar(); while(i<'0' || i>'9') i=getchar(); while(i>='0' && i<='9') ans=(ans<<1)+(ans<<3)+i-'0',i=getchar();}int tot,T;int mu[N],prime[N];lol f[N];bool vis[N];il void init() { mu[1]=1; for(rg int i=2;i<=NN;i++) { if(!vis[i]) prime[++tot]=i,mu[i]=-1; for(rg int j=1;j<=tot && prime[j]*i<=NN;j++) { vis[i*prime[j]]=1; if(i%prime[j]==0) break; else mu[i*prime[j]]=-mu[i]; } } for(rg int i=1;i<=NN;i++) { lol ans=0; mu[i]+=mu[i-1]; for(rg int l=1,r,len;l<=i;l=r+1) { r=i/(i/l),len=r-l+1; ans+=1ll*len*(i/l); }f[i]=ans; }}int main(){ in(T); init(); while(T--) { int n,m,maxn; lol ans=0; in(n),in(m); maxn=Min(n,m); for(rg int l=1,r;l<=maxn;l=r+1) { r=Min(n/(n/l),m/(m/l)); ans+=1ll*(mu[r]-mu[l-1])*f[n/l]*f[m/l]; } printf("%lld\n",ans); }}