2019年ICPC银川 Easy Problem 莫比乌斯反演+欧拉降幂+预处理

题意

$$求解\sum_{a_1=1}^m…\sum_{a_n=1}^m\prod_{i=1}^na_i^k[gcd(a_1,a_2…,a_n)=d]$$

思路

$$\sum_{a_1=1}^{\frac{m}{d}}…\sum_{a_n=1}^{\frac{m}{d}}\prod_{i=1}^na_i^kd^k[gcd(a_1,a_2…,a_n)=1]$$

$注意有一个d^k！$

$$d^k\sum_{a_1=1}^{\frac{m}{d}}…\sum_{a_n=1}^{\frac{m}{d}}\prod_{i=1}^na_i^k\sum_{ta_1…ta_n}\mu(t)$$

$变换枚举顺序：$

$$d^{nk}\sum_{t=1}^{\frac{m}{d}}\mu(t)\sum_{a_1=1}^{\frac{m}{td}}…\sum_{a_n=1}^{\frac{m}{td}}\prod_{i=1}^na_i^kt^k$$

$$d^{nk}\sum_{t=1}^{\frac{m}{d}}t^{nk}\mu(t)\sum_{a_1=1}^{\frac{m}{td}}…\sum_{a_n=1}^{\frac{m}{td}}\prod_{i=1}^na_i^k$$

$这里有一个玄学:$

$$\sum_{a_1=1}^{\frac{m}{td}}…\sum_{a_n=1}^{\frac{m}{td}}\prod_{i=1}^na_i^k=(\sum_{i=1}^{\frac{m}{td}}i^k)^n$$

$因为a可取的值再[1,\frac{m}{td}]，而后面那个你可以想成完全平方的概念，更高的数学意义就是每个数都去的所有贡献。$

$多体会体会，很黑科技。$

$最后答案为：$

$$d^{nk}\sum_{t=1}^{\frac{m}{d}}t^{nk}\mu(t)(\sum_{i=1}^{\frac{m}{td}}i^k)^n$$

$注意n要欧拉降幂处理。总复杂度为O(n*\logn*\logn+T*\frac{m}{d})$

Code

##include "bits/stdc++.h"
using namespace std;

typedef long long ll;

const int N = 1e6 + 10;

const ll mod = 59964251;
const ll phi = 59870352;

bool is\_prime[N];
int prime[N], cnt, mu[N];

void init() {
    mu[1] = 1;
    for(int i = 2;i < N; i++) {
        if(!is\_prime[i]) prime[++cnt] = i, mu[i] = -1;
        for(int j = 1;j <= cnt && i * prime[j] < N; j++) {
            is\_prime[i * prime[j]] = 1;
            if(i % prime[j] == 0) {
                mu[i * prime[j]] = 0;
                break;
            }
            else mu[i * prime[j]] = -mu[i];
        }
    }
}

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;
}

void solve() {
    init();
    int \_; cin >> \_;
    while(\_--) {
        string n; cin >> n;
        ll p = 0;
        for(int i = 0;i < n.length(); i++) {
            p = p * 10 + n[i] - '0';
            p = p % phi + phi;
        }
        ll m, k, d; cin >> m >> d >> k;
        vector<ll> f(m / d + 10), F(m / d + 10);
        for(int i = 1;i <= m / d; i++) {
            f[i] = (f[i - 1] + quick\_pow(i, k)) % mod;
            F[i] = quick\_pow(f[i], p);
        }
        ll ans = 0;
        for(int i = 1;i <= m / d; i++) {
            ans = (ans + quick\_pow(i, p * k) * mu[i] * F[m / (i * d)]) % mod;
        }
        ans = ans * quick\_pow(d, p * k) % mod;
        cout << (ans % mod + mod) % mod << endl;
    }
}

signed main() {
    solve();
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/04/11/2019-icpc-yinchuan-easy-problem/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！