题解

题意简述

给定 B，多次求 \sum\limits_{i=L}^R \varphi^{(\max_{j=1}^i \varphi(j) - B)}(i)。

日记不会这种科技，数据怎么造的？ 你不会真的认为我写的是暴力吧 /mm

知识点

质因数分解、欧拉函数、（可选）线性筛

解题思路

前置知识

为解决此题，我们首先要证明一些东西。

对一个正整数 $x$，满足 $\varphi^{(k)}(x) = 1$ 的最小正整数 $k$ 不超过 $2 \lceil{\log x}\rceil$。

证明：分类讨论。

• 当 $x \equiv 0 \pmod 2$ 时，根据 $\varphi$ 的定义式，所有形如 $2i$ 的数均不与 $x$ 互质。因此，$\varphi(x) \leq \dfrac{x}{2}$。
• 当 $x \equiv 1 \pmod 2$ 且 $x \neq 1$ 时，$\gcd(x,x) = x \neq 1$。因此，$\varphi(x) \leq x - 1$。

额外地，可以证明奇数的 $\varphi$ 函数一定为偶数。证明：若 $i$ 与 $x$ 互质，$(x-i)$ 也与 $x$ 互质。特例在 $\dfrac{x}{2}$ 处，而奇数不存在这一处。

综上，每两次迭代，$x$ 必然缩小到 $\dfrac{x}{2}$。因此，

• 事实上，可以进一步地缩小下界到 $\lceil{\log x}\rceil$，但此题不需要。

对一个正整数 $x \leq B$，$f(x) = x$。

证明：$\max_{i=1}^x \varphi(x) \leq x \leq B$，因此迭代次数非正。

对一个正整数 $x \geq B+k$，$f(x) = 1$，其中 $k$ 为一个较小常数（可视为 $500$）。

这并非一个严谨证明。考虑最小的 $p \geq B + l$（其中 $l$ 为一个更小的常数，可视为 $60$），则对一个正整数 $x \geq p$，有 $\max_{i=1}^x \varphi(x) \geq \varphi(p) = p-1 \geq B + l - 1$，因此迭代次数至少为 $l-1$。由于 $l$ 足够大（$> 2\lceil\log B\rceil$），迭代结果一定为 $1$（见第一条证明）。

下一步目标，是找到 $p - B$ 的上界。它相当于两个相邻质数差的最大值。万幸，$10^9$ 范围内，这一最大值不超过 $400$。（日记：暴力跑的）

完整做法

以上已经把题说得差不多了。我们已经对 $x \leq B$ 和 $x \geq B + k$ 的情况给出了能够达到 $O(1)$ 的做法。

剩余的数一共有 $k$ 个。考虑暴力求。利用质因数分解求 $\varphi$ 值是容易做到 $O(\sqrt{n})$ 的。而迭代次数是 $O(\log n)$ 的，这部分的复杂度为 $O(k\sqrt{n}\log n)$。

而 $B$ 固定时，这一部分是不变的。因此只需要一次预处理。总复杂度：$O(k \sqrt{n} \log n + T)$。

诈骗：答案显然不会超过 $n^2$，因此开个 long long 就行。

以上 $n$ 均指 $\max R$，即数据范围的第三列值。

标准代码

C++

#include <bits/stdc++.h>
using namespace std;

#define int long long
bool inp[1000005];
int pri[1000005], pc;
void sieve(int mx) {
  inp[0] = inp[1] = true;
  for (int i = 2; i <= mx; ++i) {
    if (!inp[i]) pri[++pc] = i;
    for (int j = 1; i * pri[j] <= mx && j <= pc; ++j) {
      inp[i * pri[j]] = true;
      if (i % pri[j] == 0) break;
    }
  }
  return;
}

bool is_prime(int x) {
  if (x <= 1) return false;
  for (int i = 1; pri[i] * pri[i] <= x; ++i) {
    if (x % pri[i] == 0) return false;
  }
  return true;
}
int phi(int x) {
  int ans = x;
  for (int i = 1; pri[i] * pri[i] <= x; ++i) {
    if (x % pri[i] == 0) {
      while (x % pri[i] == 0) {
        x /= pri[i];
      }
      ans = ans / pri[i] * (pri[i] - 1);
    }
  }
  if (x > 1) ans = ans / x * (x - 1);
  return ans;
}

int T, B;
int f(int x, int max_phi) {
  max_phi -= B;
  if (max_phi <= 0) return x;
  while (max_phi--) {
    x = phi(x);
    if (x == 1) return 1;
  }
  return x;
}

int p1, p2;
int val[1000005], ps[1000005];
int a(int x) {
  return x * (x + 1) / 2; // 1 + 2 + ... + x
}
int b(int x) {
  return ps[x - p1];
}
int c(int x) {
  return x - p2; // p2+1 p2+2 .. x
}
void pre() {
  for (int i = B; i; --i) {
    if (is_prime(i)) {
      p1 = i;
      break;
    }
  }
  for (int i = B + 60; i <= 1100000000; ++i) {
    if (is_prime(i)) {
      p2 = i;
      break;
    }
  }

  int mx = phi(p1);
  for (int i = p1; i <= p2; ++i) {
    mx = max(mx, phi(i));
    val[i - p1] = f(i, mx);
    if (i != p1) ps[i - p1] = ps[i - p1 - 1] + val[i - p1];
    else ps[i - p1] = val[i - p1];
  }
}
int solve(int x) {
  if (x < p1) return a(x);
  else if (x <= p2) return a(p1 - 1) + b(x);
  else return a(p1 - 1) + b(p2) + c(x);
}

signed main() {
  //freopen("phi.in", "r", stdin);
  //freopen("phi.out", "w", stdout);
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  sieve(1000000);
  cin >> T >> B;
  pre();
  while (T--) {
    int L, R;
    cin >> L >> R;
    cout << solve(R) - solve(L - 1) << '\n';
  }
  cout.flush();
  return 0;
}