[CF615D] Multipliers - 数论

[CF615D] Multipliers - 数论

Description

给你一个数，输出其所有因数的乘积。对\(10^9+7\)取模。这个数以质因子乘积的形式给出。

Solution

统计出每个因子出现的个数，第 \(i\) 个因子的个数记作 \(q_i\)，总的因子数的个数显然是 \(\prod_i (q_i+1)\)，于是每个因子最终贡献的幂次为 \(\frac 1 2 q_i tot\)

算幂次时根据欧拉定理，要对 \(10^9 +6\) 取模，但是这里有个除 \(2\) 很讨厌，考虑到 \(q_i\) 和 \(tot\) 中至少由一个能被 \(2\) 整除，这里我们可以先对 \(2(10^9+6)\) 取模，最后暴力除

#include 
using namespace std;

#define int long long

const int mod = 1e9 + 7;
const int MOD = (1e9 + 6) * 2;

int qpow(int p, int q)
{
    q %= MOD / 2;
    return (q & 1 ? p : 1) * (q ? qpow(p * p % mod, q / 2) : 1) % mod;
}

signed main()
{
    ios::sync_with_stdio(false);

    int n;
    cin >> n;

    map mp;
    while (n--)
    {
        int x;
        cin >> x;
        mp[x]++;
    }

    int tot = 1;
    for (auto [val, cnt] : mp)
    {
        tot *= (cnt + 1);
        tot %= MOD;
    }

    int ans = 1;
    for (auto [val, cnt] : mp)
    {
        int q = cnt;
        if (q & 1)
            q = tot / 2 % MOD * q;
        else
            q = q / 2 * (tot % MOD);
        q %= MOD;
        ans *= qpow(val, q);
        ans %= mod;
    }

    cout << ans << endl;
}