bzoj 2820

友情链接：

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

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

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

210 10100 100

302791

$T = 10000$

$N, Mle 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}^{lfloorfrac{M}{d}rfloor}[gcd(i, j)=1]\ &= sum_{i=1}^{lfloor frac{N}{d}rfloor}sum_{j=1}^{lfloorfrac{M}{d}rfloor}sum_{k|gcd(i,j)}mu(k)\ &= sum_{i=1}^{lfloor frac{N}{d}rfloor}sum_{j=1}^{lfloorfrac{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}^{lfloorfrac{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}^{lfloorfrac{M}{d}rfloor}1\ &= sum_{k=1}^{min(lfloor frac{N}{d}rfloor,lfloor frac{M}{d}rfloor)}mu(k)lfloorfrac{N}{kd}rfloorlfloorfrac{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)lfloorfrac{N}{kd}rfloorlfloorfrac{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)lfloorfrac{N}{kd}rfloorlfloorfrac{M}{kd}rfloor\ &= sum_{d=1}^{min(N,M)}is(d)sum_{d|T}mu(frac{T}{d})lfloorfrac{N}{T}rfloorlfloorfrac{M}{T}rfloor\ &= sum_{T=1}^{min(N,M)}sum_{d|T,is(d)}mu(frac{T}{d})lfloorfrac{N}{T}rfloorlfloorfrac{M}{T}rfloor\ &= sum_{T=1}^{min(N,M)}lfloorfrac{N}{T}rfloorlfloorfrac{M}{T}rfloorsum_{d|T,is(d)}mu(frac{T}{d}) end{align}$$

到这里来式子就比较明了了，$lfloordfrac{N}{T}rfloorlfloordfrac{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("%lldn", ans);
  }
  return 0;
}

刚刚开始写这种题还是要好好的把公式推一遍的。