小 Q 与函数求和 1

$\sum_{i = 1} ^{n} \sum_{j = 1} ^{n} \phi(ij \gcd(i, j) ^ K)\\ \sum_{i = 1} ^{n} \sum_{j = 1} ^{n} \gcd(i, j) ^ K \phi(ij)\\ \sum_{i = 1} ^{n} \sum_{j = 1} ^{n} \gcd(i, j) ^ K \frac{\phi(i) \phi(j) \gcd(i, j)}{\phi(\gcd(i, j))}\\ \sum_{i = 1} ^{n} \sum_{j = 1} ^{n} \gcd(i, j) ^ {K + 1} \frac{\phi(i) \phi(j)}{ \phi(\gcd(i, j))}\\ \sum_{d = 1} ^{n} d ^{K + 1} inv(\phi(d)) \sum_{i = 1} ^{\frac{n}{d}} \sum_{j = 1} ^{\frac{n}{d}} \phi(id) \phi(jd)[\gcd(i, j) = 1]\\ \sum_{d = 1} ^{n} d ^{K + 1} inv(phi(d)) \sum_{k = 1} ^{\frac{n}{d}} \phi(k) \sum_{i = 1} ^{\frac{n}{kd}} \phi(ikd) \sum_{j = 1} ^{\frac{n}{kd}} \phi(jkd)\\ T = kd，设f(T) = \sum_{i = 1} ^{\frac{n}{T}} \phi(it)\\ \sum_{T = 1} ^{n} f(T) ^ 2 \sum_{d \mid T} d ^{K + 1} inv(\phi(d)) \mu(\frac{T}{d})\\ 设g(n) = \sum_{i \mid n} i ^{K + 1}inv (\phi(i)) \mu(\frac{n}{i})\\ \sum_{i = 1} ^{n} f(i) ^ 2 g(i)即为答案$

所以预先处理 $i ^{K + 1}$ 次幂，及 $inv(\phi(i))$ ，即可 $(n \log n)$ 同时算得 $f(n)$ ，以及 $g(n)$ ，整体复杂度 $O(n \log n)$ ，稍卡常，得写 add sub 函数才能过。

#include <bits/stdc++.h>

using namespace std;

const int N = 5e6 + 10, mod = 998244353;

int prime[N], inv[N], phi[N], mu[N], f[N], g[N], a[N], n, k, cnt;

bool st[N];

inline int add(int x, int y) {
  return x + y < mod ? x + y : x + y - mod;
}

inline void Add(int &x, int y) {
  x + y < mod ? x += y : x += y - mod;
}

inline int sub(int x, int y) {
  return x >= y ? x - y : x - y + mod;
}

inline void Sub(int &x, int y) {
  x >= y ? x -= y : x += mod - y;
}

int quick_pow(int a, int n) {
  int ans = 1;
  while (n) {
    if (n & 1) {
      ans = 1ll * ans * a % mod;
    }
    a = 1ll * a * a % mod;
    n >>= 1;
  }
  return ans;
}

void init() {
  phi[1] = mu[1] = a[1] = inv[1] = 1;
  for (int i = 2; i < N; i++) {
    inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
    if (!st[i]) {
      prime[++cnt] = i;
      phi[i] = i - 1;
      mu[i] = -1;
      a[i] = quick_pow(i, k);
    }
    for (int j = 1; j <= cnt && 1ll * i * prime[j] < N; j++) {
      st[i * prime[j]] = 1;
      a[i * prime[j]] = 1ll * a[i] * a[prime[j]] % mod;
      if (i % prime[j] == 0) {
        phi[i * prime[j]] = phi[i] * prime[j];
        break;
      }
      phi[i * prime[j]] = phi[i] * (prime[j] - 1);
      mu[i * prime[j]] = -mu[i];
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = i; j <= n; j += i) {
      Add(f[i], phi[j]);
      if (mu[j / i] == 1) {
        Add(g[j], 1ll * a[i] * inv[phi[i]] % mod);
      }
      else if (mu[j / i] == -1) {
        Sub(g[j], 1ll * a[i] * inv[phi[i]] % mod);
      }
    }
  }
}

int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  scanf("%d %d", &n, &k);
  k++;
  init();
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    Add(ans, 1ll * f[i] * f[i] % mod * g[i] % mod);
  }
  printf("%d\n", ans);
  return 0;
}