Problem

Description

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

多组数据

Input Format

第一行一个整数 \(T\) 表述数据组数

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

Output Format

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

Sample

Input

2
10 10
100 100

Output

30
2791

Range

\(T=10000\)

\(N,M\le 10000000\)

Algorithm

莫比乌斯反演

Mentality

莫比乌斯反演入门题。

所谓莫比乌斯反演题，其实都是数学公式的盛宴 = = 。

题目要我们求的，显然就是这个：

\[ \sum_{i=1}^n \sum_{j=1}^m [gcd(i,j)=prime] \]

首先令 \(n\le m\) ，那么我们可以开始变化了：

\[ \sum_{p\in prime}\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=p] \]

由于 \(gcd(i,j)==p\) ，所以 \(i|p\&\&j|p\) ，那我们可以改为枚举 \(i×p,j×p\) ，则式子变为：

\[ \sum_{p\in prime}\sum_{i=1}^{\lfloor \frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{p}\rfloor}[gcd(i,j)=1] \]

接着，我们知道莫比乌斯函数 \(\mu\) 有这样一个性质：

\[ \sum_{d|n}\mu(d) =[n=1] \]

那么我们用这个东西去代 \([gcd(i,j)=1]\) ，我们就可以得到这样一个式子：

\[ \sum_{p\in prime}\sum_{i=1}^{\lfloor \frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{p}\rfloor}\sum_{d|gcd(i,j)}\mu(d) \]

这里我们考虑摆脱 \(i,j\) 的束缚，改为枚举那些在后面出现过的每个 \(\mu (d)\) ，统计它们做出的贡献。那么式子画风一变，就会这样：

\[ \sum_{p\in prime}\sum_{d=1}^n\mu(d)\sum_{i=1}^{\lfloor \frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{p}\rfloor}[d|i\&\&d|j] \]

不难发现，或者说一目了然地发现这样一件事：

\[ \sum_{i=1}^{\lfloor \frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{p}\rfloor}[d|i\&\&d|j]=\lfloor\frac{n}{pd}\rfloor*\lfloor\frac{m}{pd}\rfloor \]

式子进一步变得简洁明了了：

\[ \sum_{p\in prime}\sum_{d=1}^n\mu(d)*\lfloor\frac{n}{pd}\rfloor*\lfloor\frac{m}{pd}\rfloor \]

不过这样子的式子求起来还不是行，我们要进一步快乐化简，设 \(T=pd\) ，那么我们的式子变得如下了：

\[ \sum_{T=1}^n\sum_{p=1,p\in prime,p|T}^n\mu(\frac{T}{p})*\lfloor\frac{n}{T}\rfloor*\lfloor\frac{m}{T}\rfloor \]

由于对于同一个 \(T\) ，\(\lfloor\frac{n}{T}\rfloor*\lfloor\frac{m}{T}\rfloor\) 的值并不会发生改变，那么我们完全可以提到 \(\sum\) 外面，接下来式子变成了：

\[ \sum_{T=1}^n\lfloor\frac{n}{T}\rfloor*\lfloor\frac{m}{T}\rfloor\sum_{p=1,p\in prime,p|T}^n\mu(\frac{T}{p}) \]

那么答案就会变得非常显然了，设 \(f(T)=\sum_{p=1,p\in prime,p|T}^n\mu(\frac{T}{p})\) ，我们只需要求出 \(f(T)\) 们就行了。

不过这里还要用到一种叫做 整除分块 的东西，因为我们发现，对于某一些连续的数 \(T\) ，它们的 \(\lfloor\frac{n}{T}\rfloor*\lfloor\frac{m}{T}\rfloor\) 完全是一样的，我们只需要通过前缀和计算这一段数对应的 \(f(T)\) 的和，统一乘上 \(\lfloor\frac{n}{T}\rfloor*\lfloor\frac{m}{T}\rfloor\) 即可。

怎么计算这个玩意呢？当然是利用这样一个结论：对于 \(i\sim \lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor\) 而言，它们的 \(\lfloor\frac{n}{i}\rfloor\) 的值都是相同的。那么我们的整除结果就被分成了一段一段相同的数，是谓所谓整除分块 = = 。具体证明很简单，可以看一下这位 Dalao 的 Blog 。

完毕。

Code

#include<iostream>
#include<cstdio>
using namespace std;
int T,n,m,cnt,pri[10000001],mu[10000001],sum[10000001];
bool vis[10000001];
void init()
{
    mu[1]=1;
    for(int i=2;i<=10000000;i++)
    {
        if(!vis[i])pri[++cnt]=i,mu[i]=-1;
        for(int j=1;j<=cnt&&pri[j]*i<=10000000;j++)
        {
            vis[pri[j]*i]=true;
            if(!(i%pri[j]))break;
            mu[pri[j]*i]=-mu[i];
        }
    }//求出莫比乌斯函数
    for(int i=1;i<=cnt;i++)
        for(int j=1;j*pri[i]<=10000000;j++)
            sum[j*pri[i]]+=mu[j];//统计 f 函数
    for(int i=1;i<=10000000;i++)
        sum[i]+=sum[i-1];//统计前缀和
}
int main()
{
    freopen("2257.in","r",stdin);
    freopen("2257.out","w",stdout);
    init();//预处理前缀和啥的
    cin>>T;
    while(T--)
    {
        long long ans=0;
        scanf("%d%d",&n,&m);
        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+=1ll*(sum[r]-sum[i-1])*(n/i)*(m/i);
        }
        printf("%lld\n",ans);
    }
}

【BZOJ 2820】YY的GCD

原文：https://www.cnblogs.com/luoshuitianyi/p/10478729.html