bzoj 2820 YY的GCD（莫比乌斯反演）

Description

神犇YY虐完数论后给傻×kAc出了一题

给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对

kAc这种傻×必然不会了，于是向你来请教……

多组输入

Input

第一行一个整数T 表述数据组数

接下来T行，每行两个正整数，表示N, M

Output

T行，每行一个整数表示第i组数据的结果

Sample Input

2
10 10
100 100

Sample Output

30
2791

HINT

T = 10000

N, M <= 10000000

【思路】

　　唉？？click here

【代码】

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 const int N = 1e7+;

 ll mu[N],sum[N],su[N],sz,np[N];

 void get_mu()

 {

     int i,j;

     mu[]=;

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

         if(!np[i]) {

             su[++sz]=i;

             mu[i]=-;

         }

         for(j=;j<=sz&&i*su[j]<N;j++) {

             np[i*su[j]]=;

             if(i%su[j]==) mu[i*su[j]]=;

             else mu[i*su[j]]=-mu[i];

         }

     }

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

         for(j=su[i];j<N;j+=su[i])

             sum[j]+=mu[j/su[i]];

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

         sum[i]+=sum[i-];

 }

 ll C(int n,int m)

 {

     int i,last; ll res=;

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

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

         last=min(n/(n/i),m/(m/i));

         res+=(n/i)*(m/i)*(sum[last]-sum[i-]);

     }

     return res;

 }

 int main()

 {

     get_mu();

     int T,n,m;

     scanf("%d",&T);

     while(T--) {

         scanf("%d%d",&n,&m);

         printf("%lld\n",C(n,m));

     }

     return ;

 }