首页
关于
笔记
文章
友链

Solution -「HDU 5780」gcd

cirnovsky /

link。

钦定 i>ji>j，研究得 (xi−1,xj−1)⇌(xi−xj,xj−1)⇌(xj(xi−j−1),xj−1)(x^i-1,x^j-1)\rightleftharpoons(x^i-x^j,x^j-1)\rightleftharpoons(x^j(x^{i-j}-1),x^j-1)，注意到 (xj,xj−1)=1(x^j,x^j-1)=1 且当 (a,c)=1(a,c)=1 时 (ab,c)=(a,b)(a,c)(ab,c)=(a,b)(a,c)，则原式 ⇌(xi−j−1,xj−1)⇌(xi mod j−1,xj−1)⇌x(i,j)−1\rightleftharpoons(x^{i-j}-1,x^j-1)\rightleftharpoons(x^{i\bmod j}-1,x^j-1)\rightleftharpoons x^{(i,j)}-1。

于是题目即求 (∑i=1n∑j=1nx(i,j))−n2\left(\sum\limits_{i=1}^n\sum\limits_{j=1}^nx^{(i,j)}\right)-n^2。注意到 1⩽(i,j)⩽n1\leqslant(i,j)\leqslant n，容易想到研究每一个 (i,j)(i,j) 的贡献次数，设其为 f(x)f(x)，显然有 f(x)=∑i=1n∑j=1n[(i,j)=x]f(x)=\sum\limits_{i=1}^n\sum\limits_{j=1}^n[(i,j)=x]，观察得 f(x)=2×(∑i=1⌊nx⌋φ(i))−1f(x)=2\times\left(\sum\limits_{i=1}^{\lfloor\frac{n}{x}\rfloor}\varphi(i)\right)-1，则答案为 ∑i=1nxi⋅f(i)\sum\limits_{i=1}^nx^i\cdot f(i)，整除分块 & 等比数列求和优化即可。

#include <bits/stdc++.h>
const int MOD = 1000000007;
template <typename T>
T add(T a, T b) {
  return (a + b) % MOD;
}
template <typename T, typename... Args>
T add(T a, T b, Args... args) {
  return add(add(a, b), args...);
}
template <typename T>
T sub(T a, T b) {
  return (a + MOD - b) % MOD;
}
template <typename T>
T mul(T a, T b) {
  return a * static_cast<long long>(b) % MOD;
}
template <typename T, typename... Args>
T mul(T a, T b, Args... args) {
  return mul(mul(a, b), args...);
}
template <typename T>
void Add(T &a, T b) {
  a = add(a, b);
}
template <typename T, typename... Args>
void Add(T &a, T b, Args... args) {
  Add(a, add(b, args...));
}
template <typename T>
void Sub(T &a, T b) {
  a = sub(a, b);
}
template <typename T>
void Mul(T &a, T b) {
  a = mul(a, b);
}
template <typename T, typename... Args>
void Mul(T &a, T b, Args... args) {
  Mul(a, mul(b, args...));
}
int tag[1000100], tot, p[1000100], n, x, ph[1000100], f[1000100];
void shai(int N) {
  tag[1] = ph[1] = 1;
  for (int i = 2; i <= N; ++i) {
    if (!tag[i]) {
      p[++tot] = i;
      ph[i] = i - 1;
    }
    for (int j = 1; j <= tot && i * p[j] <= N; ++j) {
      tag[i * p[j]] = 1;
      if (i % p[j] == 0) {
        ph[i * p[j]] = ph[i] * p[j];
        break;
      }
      ph[i * p[j]] = ph[i] * ph[p[j]];
    }
  }
  for (int i = 1; i <= N; ++i) Add(ph[i], ph[i - 1]);
  for (int i = 1; i <= N; ++i) f[i] = sub(mul(ph[i], 2), 1);
}
int fp(int x, int y) {
  int res = 1;
  for (; y; y >>= 1, Mul(x, x))
    if (y & 1) Mul(res, x);
  return res;
}
int Inv(int x) { return fp(x, MOD - 2); }
int Sum(int n) { return mul(x, sub(1, fp(x, n)), Inv(sub(1, x))); }
int Sum(int l, int r) { return sub(Sum(r), Sum(l - 1)); }
signed main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  int T;
  shai(1e6);
  for (std::cin >> T; T; --T) {
    std::cin >> x >> n;
    if (x == 1) {
      std::cout << "0\n";
      continue;
    }
    int res = 0;
    for (int l = 1, r; l <= n; l = r + 1) {
      r = n / (n / l);
      Add(res, mul(Sum(l, r), f[n / l]));
    }
    std::cout << sub(res, mul(n, n)) << '\n';
  }
  return 0;
}