BZOJ2820: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

Solution

以下均为n<m。

$\sum_{p\in prime}\sum_{a=1}^n\sum_{b=1}^m[gcd(a,b)=p]$

$\sum_{p\in prime}\sum_{a=1}^{\left \lfloor \frac{n}{p} \right \rfloor}\sum_{b=1}^{\left \lfloor \frac{m}{p} \right \rfloor}[gcd(a,b)=1]$

$\sum_{p\in prime}\sum_{a=1}^{\left \lfloor \frac{n}{p} \right \rfloor}\sum_{b=1}^{\left \lfloor \frac{m}{p} \right \rfloor}\sum_{d|gcd(a,b)}\mu(d)$

$\sum_{p\in prime}\sum_{d=1}^{\left \lfloor \frac{n}{p} \right \rfloor}\mu(d){\left \lfloor \frac{n}{pd} \right \rfloor}{\left \lfloor \frac{m}{pd} \right \rfloor}$

推到这和前面做过的几个题是一样的……然后就不会了QAQ……

设$pd=T$

$\sum_{T=1}^{n}{\left \lfloor \frac{n}{T} \right \rfloor}{\left \lfloor \frac{m}{T} \right \rfloor}\sum_{p|T}\mu(\frac{T}{p})$

j接下来只需要求出$\sum_{p|T}\mu(\frac{T}{p})$的前缀和就好了。暴力枚举每个质数去更新ta的倍数即可。

Code

 #include<iostream>

 #include<cstdio>

 #define N (10000000)

 using namespace std;

 int T,n,m,vis[N+],prime[N+],mu[N+],cnt;

 long long sum[N+];

 void Get_mu()

 {

     mu[]=;

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

     {

         if (!vis[i]){prime[++cnt]=i; mu[i]=-;}

         for (int j=; j<=cnt && prime[j]*i<=N; ++j)

         {

             vis[prime[j]*i]=true;

             if (i%prime[j]==) break;

             mu[prime[j]*i]=-mu[i];

         }

     }

     for (int i=; i<=cnt; ++i)

         for (int j=; j*prime[i]<=N; ++j)

             sum[j*prime[i]]+=mu[j];

     for (int i=; i<=N; ++i) sum[i]+=sum[i-];

 }

 long long Calc(int n,int m)

 {

     long long ans=; if (n>m) swap(n,m);

     for (int l=,r; l<=n; l=r+)

     {

         r=min(n/(n/l),m/(m/l));

         ans+=(sum[r]-sum[l-])*(n/l)*(m/l);

     }

     return ans;

 }

 int main()

 {

     scanf("%d",&T);

     Get_mu();

     while (T--)

     {

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

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

     }

 }

巴特西