ZOJ 3868 GCD Expectation：容斥 + 快速冪求子集 GCD 期望

問題建模

給定集合 {a₁…a_n}，等概率隨機選非空子集，求 E[gcd^k] × (2ⁿ−1) mod 998244353。

數學推導

設 f(g) = gcd 為 g 的子集數。
令 cnt(g) = 數組中是 g 的倍數的元素個數。
則 gcd 為 g 的倍數的非空子集數 = 2^cnt(g) − 1。
容斥：f(g) = (2^cnt(g)−1) − Σ_k≥2 f(k·g)。
答案 = Σ f(g) × g^k mod P。

關鍵技術

• **快速冪** 計算 2^x mod P 及 g^k mod P。
• **線性篩** 預計算所有 cnt(g)（類似歐拉篩累加倍數）。
• 總 max(a_i) ≤ 2×10⁶，O(M log M) 可行。

代碼框架

const int MOD = 998244353;
const int MAXM = 2000000;

int cnt[MAXM + 1];
int f[MAXM + 1];

long long mod_pow(long long a, long long e) {
    long long r = 1;
    while (e) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int n, k; cin >> n >> k;
        fill(cnt, cnt + MAXM + 1, 0);
        int mx = 0;
        for (int i = 0, x; i < n; ++i) {
            cin >> x;
            cnt[x]++;
            mx = max(mx, x);
        }
        // 累加倍數
        for (int i = 1; i <= mx; ++i)
            for (int j = 2 * i; j <= mx; j += i)
                cnt[i] += cnt[j];

        long long ans = 0;
        for (int g = mx; g >= 1; --g) {
            f[g] = (mod_pow(2, cnt[g]) - 1 + MOD) % MOD;
            for (int j = 2 * g; j <= mx; j += g) {
                f[g] = (f[g] - f[j] + MOD) % MOD;
            }
            ans = (ans + 1LL * f[g] * mod_pow(g, k)) % MOD;
        }
        cout << ans << '\n';
    }
    return 0;
}