洛谷P2257 YY的GCD ($4 \mathrm{s}$)
例题
有$t\ \ (1\leq t\leq 1\mathrm{e}4)$组测试数据.每组测试数据给定$n,m\ \ (1\leq n,m\leq 1\mathrm{e}7)$,求$1\leq x\leq n,1\leq y\leq m$且$\gcd(x,y)$为素数的$(x,y)$的对数.
思路
不妨设$n\leq m$,若不然则交换.设素数$k\ \ (2\leq k\leq n)$.
$\displaystyle\sum_{i=1}^n \sum_{j=1}^m[\gcd(i,j)\in primes]=\sum_{k=1}^n \sum_{i=1}^n \sum_{j=1}^m [gcd(i,j)==k]=\sum_{k=1}^n \sum_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor}[\gcd(i,j)==1]$
$\displaystyle=\sum_{k=1}^n \sum_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor}\sum_{d\mid \gcd(i,j)}\mu(d)$.
先枚举$d$,因$d\mid \gcd(i,j)$,则$i$和$j$都是$d$的倍数.不妨将$i$和$j$的枚举上限都除以$d$,相当于将$i$变为$\left\lfloor\dfrac{i}{d}\right\rfloor\cdot d$,将$j$变为$\left\lfloor\dfrac{j}{d}\right\rfloor\cdot d$.
$\displaystyle 原式=\sum_{k=1}^n \sum_{d=1}^{\left\lfloor\frac{n}{k}\right\rfloor}\mu(d)\cdot\left\lfloor\dfrac{n}{kd}\right\rfloor\left\lfloor\dfrac{m}{kd}\right\rfloor\xlongequal{T=kd}\sum_{T=1}^n \left\lfloor\dfrac{n}{T}\right\rfloor\left\lfloor\dfrac{m}{T}\right\rfloor\cdot\sum_{k\mid T,k\in primes}\mu\left(\dfrac{T}{k}\right)$.
上式的$\displaystyle\sum_{k\mid T,k\in primes}\mu\left(\dfrac{T}{k}\right)$可预处理,用一个数组$f[]$记录素数及其倍数累加的$\mu$值,即对每个素数$k$,将其在范围内的所有倍数$T$的$f$值加$\mu\left(\dfrac{T}{k}\right)$,再求$f[]$的前缀和$pre[]$即可.
代码
const int MAXN = 1e7 + 5;
int n;
int primes[MAXN], cnt = 0;
bool vis[MAXN];
int mu[MAXN];
int f[MAXN]; // 记录素数及其倍数累加的mu值
int pre[MAXN]; // f[]的前缀和
void init() {
mu[1] = 1;
for (int i = 2; i < MAXN; i++) {
if (!vis[i]) primes[cnt++] = i, mu[i] = -1;
for (int j = 0; primes[j] * i < MAXN; j++) {
vis[primes[j] * i] = true;
if (i % primes[j] == 0) break;
mu[primes[j] * i] = -mu[i];
}
}
for (int i = 0; i < cnt; i++) { // 枚举素数
for (int j = 1; primes[i] * j <= 1e7; j++) // 枚举倍数
f[primes[i] * j] += mu[j];
}
for (int i = 1; i < MAXN; i++) pre[i] = pre[i - 1] + f[i];
}
int main() {
init();
CaseT{
int n,m; cin >> n >> m;
ll ans = 0;
if (n > m) swap(n, m); // 保证n≤m
for (int l = 1, r = 0; l <= n; l = r + 1) {
r = min(n / (n / l), m / (m / l));
ans += (ll)(pre[r] - pre[l - 1]) * (n / l) * (m / l);
}
cout << ans << endl;
}
}