牛客练习赛69 F-解方程

牛客练习赛69 F-解方程 莫比乌斯反演 + 质因子分解

题意思路Code(477MS) 传送门： https://ac.nowcoder.com/acm/contest/7329/F

题意

求解：$f_{i}mod998244353(1\le i\le n)$。

思路

$前置技能：\mu \ast I=\epsilon {\sigma }_q=i{d}_q\ast IF(n)={\sum }_{d|n}\mu (i)f(\frac{n}{d})$

$$\sum _{i|n}f(i){\sigma }_p(\frac{n}{i})={\sigma }_q(n)->(f\ast {\sigma }_p)n={\sigma }_q(n)$$

$先将\sigma 分解：$

$$(f\ast i{d}_p\ast I)n=(i{d}_q\ast I)n$$

$左右都乘上\mu :$

$$(f\ast i{d}_p)n=i{d}_q(n)$$

$$\sum _{i|n}f(i)\frac{n^p}{i^p}=n^q$$

$$\sum _{i|n}\frac{f(i)}{i^p}=n^{q-p}=i{d}_{q-p}(n)$$

$反演得：$

$$\frac{f(n)}{n^p}=\sum _{i|n}\frac{\mu (i)\ast n^{q-p}}{i^{q-p}}$$

$$\frac{f(n)}{n^q}=\sum _{i|n}\frac{\mu (i)}{i^{q-p}}$$

因为积性函数卷积性函数之后还是积性函数，所以能得到$\frac{f(n)}{n^q}$是积性函数。我们考虑与n互质的d，计算$f(d^k)$并且由莫比乌斯函数的性质得：

$$\frac{f(d^k)}{d^{kq}}=1-\frac{[k\ne 0]}{d^{q-p}}$$ $(根据上式，只有i=1或d时才\mu (i)满足，其他都是0)$

$所以再来看n，由基本算数定理得：n=p_1^{k_1}{p}_2^{k_2}...p_m^{k_m}，即：$

$$\frac{f(n)}{n^q}=\frac{f(p_1^{k_1})}{p_1^{q{k}_1}}\frac{f(p_2^{k_2})}{p_2^{q{k}_2}}...\frac{f(p_m^{k_m})}{p_m^{q{k}_m}}$$

$$\frac{f(n)}{n^q}=\prod _{d|n\&\&disaprime}(1-\frac{1}{d^{q-p}})$$

提前用欧拉筛处理$f(p^k)$即可，注意g数组的含义，因为当$i$时，$prime[j]$已经是$prime[j]\ast i$的因子的，而$f[i]$和$f[i\ast prime[j]]$两者之间的区别就是$prime[j{]}^q$，这还是比较难想到的。

Code(477MS)

#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pdd; #define INF 0x7f7f7f #define mem(a, b) memset(a , b , sizeof(a)) #define FOR(i, x, n) for(int i = x;i <= n; i++) const ll mod = 998244353; // const ll P = 1e9 + 7; // const double eps = 1e-6; // const double pi = acos(-1); const int N = 1e7 + 10; ll quick_pow(ll a, ll b) { ll ans = 1; while(b) { if(b & 1) ans = ans * a % mod; a = a * a % mod; b >>= 1; } return ans % mod; } int prime[N]; bool is_prime[N]; int cnt; ll q, p, n; ll f[N], g[N]; void Eluer() { is_prime[1] = is_prime[0] = true; f[1] = 1; for(int i = 2;i < N; i++) { if(!is_prime[i]) { prime[cnt++] = i; g[i] = quick_pow(i, q); f[i] = (g[i] - quick_pow(i, p)) % mod; } for(int j = 0;j < cnt && prime[j] * i < N; j++) { is_prime[i * prime[j]] = true; if(i % prime[j] == 0) { f[i * prime[j]] = f[i] * g[prime[j]] % mod; break; } f[i * prime[j]] = f[i] * f[prime[j]] % mod; } } } void solve() { cin >> n >> p >> q; Eluer(); ll ans = 0; for(int i = 1;i <= n; i++) { f[i] = (f[i] % mod + mod) % mod; ans ^= f[i]; } cout << ans << endl; } signed main() { ios_base::sync_with_stdio(false); //cin.tie(nullptr); //cout.tie(nullptr); #ifdef FZT_ACM_LOCAL freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); signed test_index_for_debug = 1; char acm_local_for_debug = 0; do { if (acm_local_for_debug == '$') exit(0); if (test_index_for_debug > 20) throw runtime_error("Check the stdin!!!"); auto start_clock_for_debug = clock(); solve(); auto end_clock_for_debug = clock(); cout << "Test " << test_index_for_debug << " successful" << endl; cerr << "Test " << test_index_for_debug++ << " Run Time: " << double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl; cout << "--------------------------------------------------" << endl; } while (cin >> acm_local_for_debug && cin.putback(acm_local_for_debug)); #else solve(); #endif return 0; }