P4464

已知 $n,x,y$​，求：

$$\sum_{i=1}^n \gcd(i,n)^x\text{lcm}(i,n)^y$$

$n\le 10^{18},x,y\le 2000$

毒瘤题，多来点。

先常规性地推导一下：

$$\sum_{i=1}^n \gcd(i,n)^x\text{lcm}(i,n)^y=n^y\sum_{i=1}^n i^y \gcd(i,n)^{x-y}\\ =n^y\sum_{d|n}d^x\sum_{i=1}^{n/d}[\gcd(i,n/d)=1]i^y\\ =n^y\sum_{d|n}d^x\sum_{p|\frac{n}{d}}\mu(p) p^yS^y(\frac{n}{dp})\\ S^y(n)=\sum_{i=1}^n i^y$$

注意到等幂和是 $y+1$ 次多项式，可以求出其系数，因此令：

$$S^y(n)=\sum_{i=0}^{y+1} B_in^i\\ n^y\sum_{d|n}d^x\sum_{p|\frac{n}{d}}\mu(p) p^yS^y(\frac{n}{dp})=n^y\sum_{d|n}d^x\sum_{p|\frac{n}{d}}\mu(p) p^y\sum_{i=0}^{y+1}B_i\frac{n^i}{d^ip^i}\\ =\sum_{i=0}^{y+1}B_in^{y+i}\sum_{d|n}\sum_{p|\frac{n}{d}}d^{x-i}\mu(p)p^{y-i}$$

注意到后面的东西相当于是 $d^x,\mu(p)p^y,I$ 三者的卷积，三个东西都是积性的，卷积结果也是积性的，因此直接对于每个质因子去求然后乘起来即可。

注意到有多测，等幂和的系数难以使用拉格朗日插值求出，只能使用伯努利数求，具体可以看 link 。

总复杂度 $O(y^2+T(n^{1/4}+y\omega(n))$。

const int N = 3000;
mint B[N + 5], C[N + 5][N + 5];

void init() {
  For(i, 0, N + 1) {
    C[i][0] = 1;
    For(j, 1, i) C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
  }
  For(i, 0, N) {
    B[i] = !i;
    For(j, 0, i - 1) B[i] -= C[i + 1][j] * B[j];
    B[i] /= i + 1;
  }
  B[1] += 1;
}

void Yui_Yagi() {
  ll n;
  int X, Y;
  cin >> n >> X >> Y;
  V<pr> res = NT::work(n);
  V<mint> A(Y + 5);
  mint I = 1_m / (Y + 1);
  For(i, 0, Y) A[Y - i + 1] = B[i] * C[Y + 1][i] * I;

  mint ans = 0;
  For(i, 0, Y + 1) {
    mint tmp = A[i] * (1_m * n).pow(Y + i);
    for (auto j : res) {
      mint p = (1_m * j.fi).pow(X - i), q = (1_m * j.fi).pow(Y - i);
      mint sum = 0, t = 1;
      For(x, 0, j.se) sum += t, t *= p;
      t = -q;
      For(x, 0, j.se - 1) sum += t, t *= p;
      tmp *= sum;
    }
    ans += tmp;
  }
  cout << ans << '\n';
}