用欧拉函数做这题，会发现 $\sum_{i = 1}^r \gcd(n, i) = \sum_{d | n} \frac rd \phi(d)$。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 998244353;
const int N = 1e6 + 10;
ll ans, pri[N], vis[N], phi[N], ans1;
void sieve(int n) {
  phi[1] = 1;
  for (int i = 2; i <= n; i++) {
    if (!vis[i]) {
      pri[++pri[0]] = i;
      phi[i] = i - 1;
    }
    for (int j = 1; j <= pri[0] && pri[j] * i <= n; j++) {
      vis[i * pri[j]] = 1;
      if (i % pri[j] == 0) {
        phi[i * pri[j]] = phi[i] * pri[j] % mod;
        break;
      }
      phi[i * pri[j]] = phi[i] * phi[pri[j]] % mod;
    }
  }
}
ll cphi(ll n) {
  ll ans = n;
  for (int i = 2; 1ll * i * i <= n; i++)
    if (n % i == 0) {
      ans = ans / i * (i - 1);
      while (n % i == 0) n /= i;
    }
  if (n > 1) ans = ans / n * (n - 1);
  return ans;
}
int main() {
  freopen("enclosure.in", "r", stdin);
  freopen("enclosure.out", "w", stdout);
  long long n, l, r;
  cin >> n >> l >> r;
  sieve(sqrt(n));
  for (int i = 1; 1ll * i * i <= n; i++) {
    if (n % i == 0) {
      ans = (ans + (r / i) % mod * phi[i] % mod) % mod;
      ans1 = (ans1 + ((l - 1) / i) % mod * phi[i] % mod) % mod;
      if (n / i != i) {
        if (n / i <= sqrt(n)) {
          ans = (ans + r / (n / i) % mod * phi[n / i] % mod) % mod;
          ans1 = (ans1 + (l - 1) / (n / i) % mod * phi[n / i] % mod) % mod;
        }
        else {
          ans = (ans + r / (n / i) % mod * cphi(n / i) % mod) % mod;
          ans1 = (ans1 + (l - 1) / (n / i) % mod * cphi(n / i) % mod) % mod;
        }
      }
    }
  }
  ll res1 = ((n % mod) * (r % mod)) % mod;
  res1 = (res1 + ((r % mod) * ((r + 1) % mod) % mod * 499122177 % mod) % mod) % mod;
  res1 = res1 - ans + mod;
  ll res2 = ((n % mod) * ((l - 1) % mod)) % mod;
  res2 = (res2 + (((l - 1) % mod) * ((l) % mod) % mod * 499122177 % mod) % mod) % mod;
  res2 = res2 - ans1 + mod;
  cout << (res1 - res2 + mod) % mod;
  return 0;
}

这个复杂度应该是 $O(\sigma(n)\sqrt n)$ 吧，$\sigma(n)$ 指 $n$ 的正因子个数。

然而这个似乎比容斥的 $O(\sigma(n)^2)$ 要快很多，这是为什么呢？是我复杂度求错了吗？