bzoj 2820

YY的GCD

友情链接：

HYSBZ - 2820

洛谷 P2257

神犇YY虐完数论后给傻×kAc出了一题

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

kAc这种傻×必然不会了，于是向你来请教……

多组输入

Input

第一行一个整数 $T$ 表述数据组数

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

Output

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

Sample Input

1	210 10100 100

Sample Output

Hint

$T = 10000$

$N, M\le 10000000$

题意

给定 $N, M$，求 $\sum_{i=1}^{N}\sum_{j=1}^{M}isprime(\gcd(i, j))$ 的值，即 $[1, M]$ 和 $[1, N]$ 两个区间中各取一个数，形成一个数对，且 $\gcd(i,j)$ 为质数，问这样的数对有多少个。

解决方案

考虑枚举质数 $d$ ，则原式为：

$\sum_{i=1}^{N}\sum_{j=1}^{M}isprime(\gcd(i, j))\\ = \sum_{d=1}^{\min(N,M)}is(d)\sum_{i=1}^{N}\sum_{j=1}^{M}[\gcd(i,j)=d]\\$

后面两个 $\sum$ 为：

$\begin{aligned} &\sum_{i=1}^{N}\sum_{j=1}^{M}[\gcd(i,j)=d]\\ &= \sum_{i=1}^{\lfloor \frac{N}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{M}{d}\rfloor}[\gcd(i, j)=1]\\ &= \sum_{i=1}^{\lfloor \frac{N}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{M}{d}\rfloor}\sum_{k|\gcd(i,j)}\mu(k)\\ &= \sum_{i=1}^{\lfloor \frac{N}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{M}{d}\rfloor}\sum_{k|i,k|j}\mu(k)\\ &= \sum_{k=1}^{\min(\lfloor \frac{N}{d}\rfloor,\lfloor \frac{M}{d}\rfloor)}\sum_{i=1,k|i}^{\lfloor \frac{N}{d}\rfloor} \ \sum_{j=1,k|j}^{\lfloor\frac{M}{d}\rfloor}\mu(k)\\ &= \sum_{k=1}^{\min(\lfloor \frac{N}{d}\rfloor,\lfloor \frac{M}{d}\rfloor)}\mu(k)\sum_{i=1,k|i}^{\lfloor \frac{N}{d}\rfloor} \ \sum_{j=1,k|j}^{\lfloor\frac{M}{d}\rfloor}1\\ &= \sum_{k=1}^{\min(\lfloor \frac{N}{d}\rfloor,\lfloor \frac{M}{d}\rfloor)}\mu(k)\lfloor\frac{N}{kd}\rfloor\lfloor\frac{M}{kd}\rfloor \end{aligned}$

$\therefore $ 原式为：

$\begin{align} &\sum_{d=1}^{\min(N,M)}is(d)\sum_{i=1}^{N}\sum_{j=1}^{M}[\gcd(i,j)=d]\\ &= \sum_{d=1}^{\min(N,M)}is(d)\sum_{k=1}^{\min(\lfloor \frac{N}{d}\rfloor,\lfloor \frac{M}{d}\rfloor)}\mu(k)\lfloor\frac{N}{kd}\rfloor\lfloor\frac{M}{kd}\rfloor\\ \end{align}$

令 $T = kd$ ，则有：

$\begin{align} &\sum_{d=1}^{\min(N,M)}is(d)\sum_{k=1}^{\min(\lfloor \frac{N}{d}\rfloor,\lfloor \frac{M}{d}\rfloor)}\mu(k)\lfloor\frac{N}{kd}\rfloor\lfloor\frac{M}{kd}\rfloor\\ &= \sum_{d=1}^{\min(N,M)}is(d)\sum_{d|T}\mu(\frac{T}{d})\lfloor\frac{N}{T}\rfloor\lfloor\frac{M}{T}\rfloor\\ &= \sum_{T=1}^{\min(N,M)}\sum_{d|T,is(d)}\mu(\frac{T}{d})\lfloor\frac{N}{T}\rfloor\lfloor\frac{M}{T}\rfloor\\ &= \sum_{T=1}^{\min(N,M)}\lfloor\frac{N}{T}\rfloor\lfloor\frac{M}{T}\rfloor\sum_{d|T,is(d)}\mu(\frac{T}{d}) \end{align}$

到这里来式子就比较明了了，$\lfloor\dfrac{N}{T}\rfloor\lfloor\dfrac{M}{T}\rfloor$ 是很明显的分块，可以办到 $O(\sqrt{n})$ 的复杂度，后面那一部分如何处理？

可以考虑枚举质数进行打表，$n$ 范围内的质数有 $\dfrac{n}{\ln n}$ 个，而用每一个质数去筛，均摊到每一个质数的复杂度为 $O(\ln n)$ ，所以线性筛出所有质数，然后用这些质数再去筛的复杂度为 $O(n)$ ，总的时间复杂度为 $O(\sqrt{n})$

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1e7 + 10;

bool vis[maxn];
int prime[maxn];
int mu[maxn];
ll f[maxn];
int tot;

void eular() {
  vis[0] = vis[1] = true;
  mu[1] = 1;
  for (int i = 2; i < maxn; i++) {
    if (!vis[i]) {
      prime[tot++] = i;
      mu[i] = -1;
    }
    for (int j = 0; j < tot && i * prime[j] < maxn; j++) {
      vis[i * prime[j]] = true;
      mu[i * prime[j]] = -mu[i];
      if (i % prime[j] == 0) {
        mu[i * prime[j]] = 0;
        break;
      }
    }
  }
}

void init() {
  for (int i = 0; i < tot; i++) {
    for (int j = prime[i]; j < maxn; j += prime[i]) {
      f[j] += mu[j / prime[i]];
    }
  }
  for (int i = 1; i < maxn; i++) {
    f[i] += f[i - 1];
  }
}

int main() {
  eular();
  init();
  int T;
  scanf("%d", &T);
  while (T--) {
    int n, m;
    scanf("%d%d", &n, &m);
    int tmp = min(n, m);
    ll ans = 0;
    for (int l = 1, r; l <= tmp; l = r + 1) {
      r = min(n / (n / l), m / (m / l));
      ans += (f[r] - f[l - 1]) * (n / l) * (m / l);
    }
    printf("%lld\n", ans);
  }
  return 0;
}