Problem
Description
给定(N), (M),求(1le xle N), (1le yle 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,Mle 10000000)
Algorithm
莫比乌斯反演
Mentality
莫比乌斯反演入门题。
所谓莫比乌斯反演题,其实都是数学公式的盛宴 = = 。
题目要我们求的,显然就是这个:
首先令 (nle m) ,那么我们可以开始变化了:
由于 (gcd(i,j)==p) ,所以 (i|p&&j|p) ,那我们可以改为枚举 (i×p,j×p) ,则式子变为:
接着,我们知道莫比乌斯函数 (mu) 有这样一个性质:
那么我们用这个东西去代 ([gcd(i,j)=1]) ,我们就可以得到这样一个式子:
这里我们考虑摆脱 (i,j) 的束缚,改为枚举那些在后面出现过的每个 (mu (d)) ,统计它们做出的贡献。那么式子画风一变,就会这样:
不难发现,或者说一目了然地发现这样一件事:
式子进一步变得简洁明了了:
不过这样子的式子求起来还不是行,我们要进一步快乐化简,设 (T=pd) ,那么我们的式子变得如下了:
由于对于同一个 (T) ,(lfloorfrac{n}{T} floor*lfloorfrac{m}{T} floor) 的值并不会发生改变,那么我们完全可以提到 (sum) 外面,接下来式子变成了:
那么答案就会变得非常显然了,设 (f(T)=sum_{p=1,pin prime,p|T}^nmu(frac{T}{p})) ,我们只需要求出 (f(T)) 们就行了。
不过这里还要用到一种叫做 整除分块
的东西,因为我们发现,对于某一些连续的数 (T) ,它们的 (lfloorfrac{n}{T}
floor*lfloorfrac{m}{T}
floor) 完全是一样的,我们只需要通过前缀和计算这一段数对应的 (f(T)) 的和,统一乘上 (lfloorfrac{n}{T}
floor*lfloorfrac{m}{T}
floor) 即可。
怎么计算这个玩意呢?当然是利用这样一个结论:对于 (isim lfloorfrac{n}{lfloorfrac{n}{i} floor} floor) 而言,它们的 (lfloorfrac{n}{i} floor) 的值都是相同的。那么我们的整除结果就被分成了一段一段相同的数,是谓所谓整除分块 = = 。具体证明很简单,可以看一下这位 Dalao 的 Blog 。
完毕。
Code
#include <cstdio>
#include <iostream>
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
", ans);
}
}