小 Q 與函數求和 1

$$\begin{gathered} \sum _{i=1}^n\sum _{j=1}^n?(ij\gcd (i,j{)}^K) \\ \sum _{i=1}^n\sum _{j=1}^n\gcd (i,j{)}^K?(ij) \\ \sum _{i=1}^n\sum _{j=1}^n\gcd (i,j{)}^K\frac{?(i)?(j)\gcd (i,j)}{?(\gcd (i,j))} \\ \sum _{i=1}^n\sum _{j=1}^n\gcd (i,j{)}^{K+1}\frac{?(i)?(j)}{?(\gcd (i,j))} \\ \sum _{d=1}^n{d}^{K+1}inv(?(d))\sum _{i=1}^{\frac{n}{d}}\sum _{j=1}^{\frac{n}{d}}?(id)?(jd)[\gcd (i,j)=1] \\ \sum _{d=1}^n{d}^{K+1}inv(phi(d))\sum _{k=1}^{\frac{n}{d}}?(k)\sum _{i=1}^{\frac{n}{kd}}?(ikd)\sum _{j=1}^{\frac{n}{kd}}?(jkd) \\ T=kd，設f(T)=\sum _{i=1}^{\frac{n}{T}}?(it) \\ \sum _{T=1}^{n}f(T{)}^2\sum _{d\mid T}{d}^{K+1}inv(?(d))\mu (\frac{T}{d}) \\ 設g(n)=\sum _{i\mid n}{i}^{K+1}inv(?(i))\mu (\frac{n}{i}) \\ \sum _{i=1}^{n}f(i{)}^{2}g(i)即為答案 \end{gathered}$$
所以預先處理$i^{K+1}$次冪，及$inv(?(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; }

總結

以上是生活随笔為你收集整理的小 Q 与函数求和 1（牛客练习赛 81 E）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。