P9920 学习笔记

五年级蒟蒻的第一篇黑题题解，求过，求赞。

顺着做题计划做题，顺便补一下这周掉的一点点社贡分。

这个题跟我从早上 \(8\) 点纠缠到晚上 \(10\) 点，题挺好，就是这个 Subtask 分治有点恶心。

题意

给定一个积性函数 \(f(x)\)，但不保证 \(f(1)=1\)，给定莫比乌斯变换

\[g(x)=\sum_{d \mid x} f(d) \]

中的 \(k\) 组值，接下来 \(t\) 组询问，每组询问给定一个 \(n\)，求 \(f(n) \bmod 998244353\)。

前置芝士

• 常见狄利克雷卷积；
• 莫比乌斯函数 \(\mu(n)\)；
• Miller-Rabin 素性测试；
• Pollard-rho 大数分解。

下面将逐一分析每一个 Subtask 的解法。

本文中的质因数分解（试除法，Miller-Rabin 素性测试，Pollard_rho 大数分解）为简洁，均用一个函数实现，相关函数如下：

std::mt19937_64rng(std::chrono::steady_clock::now().time_since_epoch().count());
bool Miller_Rabin(std::int64_t n){if (n < 2 || !(n & 1)) return false;if (n == 2 || n == 3) return true;std::int64_t d = n - 1, s = 0;while (!(d & 1)) d >>= 1, ++s;static std::int64_t bases[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};for (std::int64_t a : bases)if (a % n){std::int64_t x = binpow(a, d, n); bool flag = false;if (x == 1 || x == n - 1) continue;for (std::int64_t r = 1; r < s; r++){x = (int128)x * x % n;if (x == n - 1){ flag = true; break; }}if (!flag) return false;}return true;
}
std::int64_t Pollard_rho(std::int64_t n){if (!(n & 1)) return 2;if (!(n % 3)) return 3;while (true){std::int64_t c = std::uniform_int_distribution <std::int64_t> (1, n - 1) (rng);auto f = [&] (std::int64_t x){ return ((int128)x * x % n + c) % n; };std::int64_t x = std::uniform_int_distribution <std::int64_t> (2, n - 2) (rng);std::int64_t y = x, d = 1;while (d == 1) x = f(x), y = f(f(y)), d = std::gcd(std::abs(x - y), n);if (d != n) return d;}
} 
void fac_rec(std::int64_t n, std::map <std::int64_t, std::int64_t>& res){if (n == 1) return;if (Miller_Rabin(n)) return void(res[n]++);std::int64_t d = Pollard_rho(n);fac_rec(d, res), fac_rec(n / d, res);
}
std::map <std::int64_t, std::int64_t> fac(std::int64_t n){ // 均放在该函数中实现std::map <std::int64_t, std::int64_t> res;for (std::int64_t p = 2; p <= 1e6 && p * p <= n; p++)if (n % p == 0){std::int64_t exps = 0;while (n % p == 0) n /= p, ++exps;res[p] = exps;}if (n > 1){if (Miller_Rabin(n)) res[n] = 1;else fac_rec(n, res);}return res;
}

\(\text{Epsilion}\)

• 数据范围：\(n \le 10^6,k=100,t=10\)。

我们发现 \(g(n)=\varepsilon(n)\)，于是 \(f=g*\mu=\varepsilon*\mu=\mu\)，又因为 \(n=10^6\)，线性筛预处理即可，时间复杂度 \(O(n)\)。

void sieve(std::int64_t n){mu[1] = 1;for (std::int64_t i = 2; i <= n; i++){if (!vis[i]) prime[++tot] = i, mu[i] = -1;for (std::int64_t j = 1; j <= tot && i * prime[j] <= n; j++){vis[i * prime[j]] = true;if (i % prime[j] == 0){mu[i * prime[j]] = 0;break;} mu[i * prime[j]] = -mu[i];}}
}
void Epsilon(){sieve(maxn - 5);for (std::int64_t i = 1; i <= t; i++)if (query[i] == 1) std::cout << 1 << std::endl;else std::cout << (mu[query[i]] + mod) % mod << std::endl;
}

\(\text{Division}\)

• 数据范围：\(n \le 10^{9},k=100,t=10\)。

注意到 \(g(n)=d(n)\)，从而 \(f(n)=1\)，于是所有询问均输出 \(1\) 即可。

void Division(){for (std::int64_t i = 1; i <= t; i++)std::cout << 1 << std::endl;
}

\(\text{Unknown}\)

• 数据范围：\(n \le 10^{18},k=1,t=10\)。

这个 \(n\) 弄这么大是何意味呢，我们发现仅给出了 \(g(1)=0\)，从而 \(f(1)=0\)，积性得 \(f(n)=0\)，于是所有询问均输出 \(0\) 即可。

void Unknown(){for (std::int64_t i = 1; i <= t; i++)std::cout << 0 << std::endl;
}

\(\text{Random}\)

• 数据范围：\(n \le 10^5,k=10^5,t=10^5\)。

我们观察数据范围发现 \(n \le k\)，即所有询问的 \(n\) 均已给出，反演：

\[f(n)=g(n)-\sum_{d \mid n,d<n} f(d) \]

从小到大递推计算 \(f(i),1\le i\le k\) 即可，时间复杂度 \(O(k \log k)\)。

void Random(){for (std::int64_t i = 1; i <= k; i++)g[giv[i].first] = giv[i].second % mod;f[1] = g[1];for (std::int64_t i = 2; i <= k; i++){f[i] = g[i];for (std::int64_t j = 1; j * j <= i; j++)if (i % j == 0){if (j != i) f[i] = (f[i] - f[j]) % mod;if ((i / j) != i && (i / j) != j) f[i] = (f[i] - f[i / j]) % mod;}}for (std::int64_t i = 1; i <= t; i++)if (query[i] <= k) std::cout << (f[query[i]] + mod) % mod << std::endl;else std::cout << 0 << std::endl;
}

\(\text{Double}\)

• 数据范围：\(n \le 10^9,k=100,t=10\)。

对于已知的 \(g\) 做一次莫比乌斯反演 \(h=g*\mu\)，发现并没有什么屌用，再反演一次得到 \(p=h*\mu\)，结果均为完全平方数，开方后得到 \(\varphi(n)^2\)，从而 \(f=\varphi*1\)，即

\[f(n)=\sum_{d \mid n} \varphi(d)^2 \]

由于 \(n \le 10^9\)，我们直接对于询问做质因子分解，利用积性有

\[f(p^e)=\sum_{i=0}^e \varphi(p^i)^2=1+\sum_{i=1}^e (p^{i-1}(p-1))^2 \]

然后

\[f(n)=\prod f(p^e) \]

试除法试到 \(10^6\)，剩余部分 Miller-Rabin 素性测试即可，可以做到 \(O(\sqrt n)\)。

void Double(){auto pows = [&](std::int64_t p, std::int64_t e) ->std::int64_t{std::int64_t res = 1, phi = 1, pk = 1;for (std::int64_t i = 1; i <= e; i++){pk = pk * p % mod;if (i == 1) phi = (p - 1) % mod;else phi = phi * p % mod;res = (res + phi * phi) % mod;}return res;};for (std::int64_t i = 1; i <= t; i++){std::int64_t ans = 1;for (auto [p, e] : fac(query[i])) ans = ans * pows(p % mod, e) % mod;std::cout << ans << std::endl;}
}

\(\text{Hack}\)

• 数据范围：\(n \le 10^9,k=31623,t=1\)。

观察反演后的结果，有 \(f(p^k)=p^{2k-1}\)，对于 \(n=pq\)，其中 \(p,q\) 为质数，有 \(f(n)=n\)。

我们对于询问分解质因数，如果仅有两个质因子且质数均为 \(1\)，直接输出 \(n \bmod 998244353\)，否则计算 \(\prod p^{2e-1} \bmod 998244353\)，由于 \(n \le 10^9\)，试除加上 Miller-Rabin 素性测试即可，可以做到 \(O(\sqrt n)\)。

void Hack(){for (std::int64_t i = 1; i <= t; i++){auto fs = fac(query[i]);if (fs.size() == 2 && fs.begin()->second == 1 && std::next(fs.begin())->second == 1) std::cout << query[i] % mod << std::endl;else {std::int64_t ans = 1;for (auto [p, e] : fs) ans = ans * binpow(p % mod, 2 * e - 1, mod) % mod;std::cout << ans << std::endl;}}
}

\(\text{Square}\)

• 数据范围：\(n \le 10^{18},k=100,t=5\)。

我们发现 \(g(n)=n^2\)，反演 \(f=g*\mu\)，即

\[f(n)=\sum_{d \mid n} d^2\mu(\frac nd) \]

根据积性，有

\[f(p^k)=p^{2k}-p^{2k-2} \]

于是

\[f(n)=n^2 \prod_{p \mid n} (1-p^{-2}) \]

对于每个询问用 Pollard-Rho 分解质因数，计算上式，注意求逆元，这样速度快得飞起，为 \(O(n^{1/4})\)。

void Square(){for (std::int64_t i = 1; i <= t; i++){auto fs = fac(query[i]);auto ans = (query[i] % mod) * (query[i] % mod) % mod;for (auto [p, e] : fs){std::int64_t inv = binpow(p % mod, mod - 2, mod);inv = inv * inv % mod;ans = ans * ((1 - inv + mod) % mod) % mod;}std::cout << ans << std::endl;}
}

\(\text{Poly}\)

• 数据范围：\(n \le 10^9,k=10^5,t=100\)。

注意到 \(f(p^k)\) 为关于 \(p^k\) 的三次多项式，即

\[f(p^k)=114p^{3k}+514p^{2k}+1919p^k+810 \]

（上述多项式系数由拉格朗日插值得出，参见学习笔记）

对询问的 \(n\) 分解质因数，对每个 \(p^e\) 代入多项式求值，乘起来即可，可以做到 \(O(\sqrt n)\)。

\(\text{Thanks}\)

• 数据范围：\(n \le 10^5,k=4,t=10^5\)。

给了四个已知的 \(g\) 值，我们手算有 \(f(1)=f(2)=f(4)=1,f(3)=0,f(5)\) 无法确定，我们猜测 \(f(n)=n^2 \bmod 3\)，符合积性。

void Thanks(){for (std::int64_t i = 1; i <= t; i++) std::cout << ((query[i] % 3) * (query[i] % 3) % 3) << std::endl;
}

无注释纯享版代码。