一个下午摸不到键盘系列。
看题解推柿子要爆炸。。
推到吐了，看到最后又变成约数个数心里一万只cnm飞过。。所以在电脑上就不重写了。
觉得这一辈子都不会忘记约数个数公式了。。
有(si)用(ji)的东(gong)西(shi)：
d(nm)= sigema(x|n) sigema(y|m) [gcd(x,y)==1]
sigema(x|n) u(x)=[n==1] 比如 sigema(x|gcd(a,b))u(x)=[gcd(a,b)==1] 在这里上限就是min(a的上限，b的上限)
n的约数个数也等于这个:sigema(1~n)i (n/i) （向下整除）
然后学会了线筛约数。
#include#include #include #include #include #include using namespace std;typedef long long LL;int pr,prime[51000];bool v[51000];LL u[51000],yue[51000],cs[51000];void f__klajiti(){ pr=0; memset(v,true,sizeof(v));v[1]=false; u[1]=1;yue[1]=1; for(int i=2;i<=50000;i++) { if(v[i]==true) { prime[++pr]=i; u[i]=-1; yue[i]=2; cs[i]=1; } for(int j=1;j<=pr&&i*prime[j]<=50000;j++) { v[i*prime[j]]=false; if(i%prime[j]==0) { u[i*prime[j]]=0; yue[i*prime[j]]=yue[i]/(cs[i]+1)*(cs[i]+2); cs[i*prime[j]]=cs[i]+1; break; } u[i*prime[j]]=-u[i]; yue[i*prime[j]]=yue[i]*2; cs[i*prime[j]]=1; } u[i]+=u[i-1]; yue[i]+=yue[i-1]; }}int main(){ f__klajiti(); int T_TzzLmy; scanf("%d",&T_TzzLmy); while(T_TzzLmy--) { int n,m; scanf("%d%d",&n,&m); if(n>m)swap(n,m); LL LJHHN=0;int last=0; for(int d=1;d<=min(n,m);d=last+1) { last=min(n/(n/d),m/(m/d)); LJHHN+=(u[last]-u[d-1])*yue[n/d]*yue[m/d]; } printf("%lld\n",LJHHN); } return 0;}