牛客练习赛69 F-解方程

jujimeizuo

2020-10-03

ACM

传送门：https://ac.nowcoder.com/acm/contest/7329/F

题意

求解： $f_i\;\;mod\;\;998244353\;\;(1\leq i\leq n)$ 。

思路

前置技能： $\mu*I =\varepsilon \;\;\;\; \sigma _q=id_q*I\;\;\;\;F(n)=\sum_{dn}\mu(i)f(\frac{n}{d})$

$\sum_{in}f(i)\sigma_p(\frac{n}{i})=\sigma _q(n)\;\;->\;\;(f*\sigma_p )n=\sigma_q(n)$

先将 $\sigma$ 分解：

$(f*id_p*I)n=(id_q*I)n$

左右都乘上 $\mu:$

$(f*id_p)n=id_q(n)$

$\sum_{in}f(i)\frac{n^p}{i^p}=n^q$

$\sum_{in}\frac{f(i)}{i^p}=n^{q-p}=id_{q-p}(n)$

反演得：

$\frac{f(n)}{n^p}=\sum_{in}\frac{\mu(i)*n^{q-p}}{i^{q-p}}$

$\frac{f(n)}{n^q}=\sum_{in}\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^{qk_1}}\frac{f(p_2^{k_2})}{p_2^{qk_2}}…\frac{f(p_m^{k_m})}{p_m^{qk_m}}$

$\frac{f(n)}{n^q}=\prod_{dn \&\&d\;is\;a\;prime}(1-\frac{1}{d^{q-p}})$

提前用欧拉筛处理 $f(p^k)$ 即可，注意g数组的含义，因为当 $i%prime[j]=0$ 时， $prime[j]$ 已经是 $prime[j]*i$ 的因子的，而 $f[i]$ 和 $f[i*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;
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2020/10/03/nowcoder-practice69-f/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！