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

Description

 设d(x)为x的约数个数，给定N、M，求  

 

Input

输入文件包含多组测试数据。

第一行，一个整数T，表示测试数据的组数。

接下来的T行，每行两个整数N、M。

 

Output

T行，每行一个整数，表示你所求的答案。

 

Sample Input

2
7 4
5 6

Sample Output

110
121

HINT

1<=N, M<=50000

1<=T<=50000

 

 

数论……终于还是的在神犇博客的帮助下才写得出……T_T……

最后推出一个式子ans=sigma(miu(i)*f(n/i)*f(m/i))，其中f(m/i)为d数组的前缀和……还有个优化是把n/i卡成数段再加起来……

 

#include<cstdio>

#include<algorithm>

using namespace std;

int t,n,m,p[],u[],s[],f[],num=,o,an[],xn,xm;

long long ans;

bool bo[];

char ch;

inline int min(int x,int y){return x<y?x:y;}

inline int read(){

    o=;ch=getchar();

    while (ch<''||ch>'') ch=getchar();

    while (ch>=''&&ch<='') o=o*+ch-, ch=getchar();

    return o;

}

int main(){

    scanf("%d",&t);

    u[]=;s[]=;

    register int i,j;

    for (i=;i<=;i++){

        if (!bo[i]) p[num++]=i,u[i]=-,s[i]=,f[i]=;

        for (j=;j<num;j++){

            o=i*p[j];

            if (o>) break;

            bo[o]=;

            if (i%p[j]) u[o]=-u[i],s[o]=s[i]*,f[o]=;else{

                u[o]=;

                s[o]=s[i]/(f[i]+)*(f[i]+);

                f[o]=f[i]+;

            }

        }

        s[i]+=s[i-];u[i]+=u[i-];

    }

    while(t--){

        n=read();m=read();

        if (n>m) swap(n,m);

        ans=;

        for (i=;i<=n;i=j+) xn=n/i,xm=m/i,j=min(n/xn,m/xm),ans+=((long long)((u[j]-u[i-])*s[xn])*s[xm]);

        printf("%lld\n",ans);

    }

}