洛谷：P1593：因子和

题目

P1593：因子和

分析

这也是一道纯粹的数论题。

快速幂运算

虽然C++有内置的pow函数，但并不适用这个场景：在计算\(a^b\)时就可能超出了范围，也就无法再求模。我们必须写自己的幂运算函数。

快速幂算法基于以下数学性质：

1. 任何数的0次方等于1
2. 对于任意正整数\(n\)，\(a^n\)可以分解为：
   • 如果n是偶数：\(a^n = (a^{n/2})^2\)
   • 如果n是奇数：\(a^n = a * (a^{n/2})^2\)

代码如下：¹

ll modpow(ll base, ll exp)
{
    ll res = 1;
    while (exp > 0)
    {
        if (exp & 1)
            res = res * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return res;
}

唯一分解定律

对于任意一个正整数\(n\)，都可以分解为若干个质数的幂的乘积：\(n = p_1^{a_1} * p_2^{a_2} * ... * p_k^{a_k}\)，其中\(p_i\)是质数，\(a_i\)是正整数，而且这个分解是唯一的。

那么对于\(a^b\)来说，它可以被唯一分解为：\(A^B = p_1^{a_1×B} × p_2^{a_2×B} × ... × p_k^{e_k×B}\)。

进一步推导，\(a^b\)的约数和（Sum）就是：\(Sum(a^b)=(1+p_1+p_1^2+...+p_1^{a_1b})\times(1+p_2+p_2^2+...+p_2^{a_2b})\times ... \times (1+p_k+p_k^2+...+p_k^{a_kb})\)。

这里出现了很多等比数列求和的运算：\(\sum_{i=0}^n p^i = \frac{p^{n+1}-1}{p-1}\)。

费马小定理

上面的“唯一分解定理”给出了计算因子和的思路，但出于两个原因，我们不能直接运算：我们要考虑计算结果范围，以及更麻烦的求模。

考虑到乘法的求模符合结合律：\((a\times b)\%c=a\%c\times b\%c\)，所以如果能将除法改为乘法的话，就会简单很多。由此我们需要引入“费马小定理”。

费马小定理是一个很重要的定理：如果\(p\)是一个质数，且\(a\)不能被\(p\)整除，那么：

\(a^{p-1} \equiv 1 \pmod{p}\)

所以当我们遇到分母\(p-1\)时，可以利用费马小定理计算它在模\(M\)意义下的乘法逆元。设：

\(S \equiv \frac{p^{(exp+1)} - 1}{p - 1} \pmod{MOD}\)

根据费马小定理，\(\frac{a}{b} \pmod{m} \equiv a \times b^{-1} \pmod{m}\)，其中\(b^{-1}\)是\(b\)在模\(m\)下的乘法逆元，满足\(b \times b^{-1} \equiv 1 \pmod{m}\)。所以我们的公式变为：

\(S \equiv (p^{(exp+1)} - 1) \times (p - 1)^{-1} \pmod{MOD}\)

再套用一次费马小定理，

\(a^{(p-2)} \equiv a^{-1} \pmod{p}\)

因此，\((p-1)\) 在模\(MOD\)下的乘法逆元为：\((p-1)^{-1} \equiv (p-1)^{(MOD-2)} \pmod{MOD}\)

综合起来

将上述推导应用到我们的公式中：

1. 计算分子： (modpow(p, exp + 1) - 1 + MOD) % MOD
   • 这里的+ MOD 是为了确保结果为正（防止减法导致负数）
   • % MOD确保结果在模 \(MOD\) 范围内
2. 计算\((p-1)\)的乘法逆元：modpow(p - 1, MOD - 2) % MOD
   • 使用费马小定理计算 \((p-1)^{(MOD-2)} \pmod{MOD}\)
3. 将分子乘以逆元并取模： ... * modpow(p - 1, MOD - 2) % MOD
   最终得到的表达式就是：

ll geo_sum(ll p, ll exp)
{
    if (p == 1)
        return 1;
    return (modpow(p, exp + 1) - 1 + MOD) % MOD * modpow(p - 1, MOD - 2) % MOD;
}

特殊处理

对于b==1的情况，我们可以直接找因子；但对于b>1的情况我们需要进行复杂的计算。

答案

思考

（略）