bzoj:3994:vijos1949: [SDOI2015]约数个数和

#include<cstdio>
#include<algorithm>
using namespace std;
int t,n,m,p[10001],u[50001],s[50001],f[50001],num=0,o,an[22],xn,xm;
long long ans;
bool bo[50001];
char ch;
inline int min(int x,int y){return x<y?x:y;}
inline int read(){
    o=0;ch=getchar();
    while (ch<‘0‘||ch>‘9‘) ch=getchar();
    while (ch>=‘0‘&&ch<=‘9‘) o=o*10+ch-48, ch=getchar();
    return o;
}
int main(){
    scanf("%d",&t);
    u[1]=1;s[1]=1;
    register int i,j;
    for (i=2;i<=50000;i++){
        if (!bo[i]) p[num++]=i,u[i]=-1,s[i]=2,f[i]=1;
        for (j=0;j<num;j++){
            o=i*p[j];
            if (o>50000) break;
            bo[o]=1;
            if (i%p[j]) u[o]=-u[i],s[o]=s[i]*2,f[o]=1;else{
                u[o]=0;
                s[o]=s[i]/(f[i]+1)*(f[i]+2);
                f[o]=f[i]+1;
            }
        }
        s[i]+=s[i-1];u[i]+=u[i-1];
    }
    while(t--){
        n=read();m=read();
        if (n>m) swap(n,m);
        ans=0;
        for (i=1;i<=n;i=j+1) xn=n/i,xm=m/i,j=min(n/xn,m/xm),ans+=((long long)((u[j]-u[i-1])*s[xn])*s[xm]);
        printf("%lld\n",ans);
    }
}