博客

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

Source

跟这个一样：


【bzoj2818】Gcd 欧拉函数

不过是多组数据，每组不能O(n)做了…

所以这样：

$$\sum_{p是素数}\sum_{i<=n}\sum_{j<=m}gcd(i,j)=p$$

$$=\sum_{p是素数}\sum_{i<=n/p}\sum_{j<=m/p}e(gcd(i,j))$$

$$=\sum_{p是素数}\sum_{i<=n/p}\sum_{j<=m/p}\sum_{d|i \ d|j}\mu(d)$$

$$=\sum_{p是素数}\sum_{d<=min(n/p,m/p)}\mu(d)\sum_{i<=n/p}\sum_{j<=m/p}[d|i \ d|j]$$

$$=\sum_{p是素数}\sum_{d<=min(n/p,m/p)}\mu(d) * \lfloor\frac{n}{pd}\rfloor * \lfloor\frac{m}{pd}\rfloor$$

令








k


=


p


d












$k=pd$
。

$$=\sum_{p是素数}\sum_{k<=min(n,m)}^{p|k}\mu(\frac{k}{p}) * \lfloor\frac{n}{k}\rfloor * \lfloor\frac{m}{k}\rfloor$$

设








f




(


k


)


=





∑








p




|




k










p





是








素








数












μ


(





k






p













)










$f(k)=\sum_{p是素数}^{p|k}\mu(\frac{k}{p})$
。

所以答案就是

$$\sum_{k<=min(n,m)}f(k) * \lfloor\frac{n}{k}\rfloor * \lfloor\frac{m}{k}\rfloor$$

f




(


k


)










$f(k)$
可以筛。

然后就能








O


(






n













√







)










$O(\sqrt n)$
回答了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;

typedef long long LL;

const int SZ = 10000010;
const int MAXN = 10000000;

bool vis[SZ];
int pri[SZ],mu[SZ];
LL f[SZ],sum[SZ];

void shai()
{
    mu[1] = 1;
    int tot = 0;
    for(int i = 2;i <= MAXN;i ++)
    {
        if(!vis[i]) pri[++ tot] = i,mu[i] = -1;
        for(int j = 1,m;j <= tot && (m = i * pri[j]) <= MAXN;j ++)
        {
            vis[m] = 1;
            if(i % pri[j] == 0) { mu[m] = 0; break; }
            else mu[m] = -mu[i];
        }
    }
    for(int i = 1;i <= tot;i ++)
    {
        for(int j = pri[i];j <= MAXN;j += pri[i])
        {
            f[j] += mu[j / pri[i]];
        }
    }
    for(int i = 1;i <= MAXN;i ++)
        sum[i] = sum[i - 1] + f[i];
}

LL ask(int n,int m)
{
    LL ans = 0;
    if(n > m) swap(n,m);
    for(int i = 1,r;i <= n;i = r + 1)
    {
        r = min(n / (n / i),m / (m / i));
        ans += (sum[r] - sum[i - 1]) * (n / i) * (m / i);
    }
    return ans;
}

int main()
{
    int T;
    scanf("%d",&T);
    shai();
    while(T --)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        printf("%lld\n",ask(n,m));
    }
    return 0;
}