分治(等比数列求和) - 约数之和 - AcWing 97

分治(等比数列求和) - 约数之和 - AcWing 97

题意：

假设现在有两个自然数A和B，S是 A^B 的所有约数之和。

请你求出S mod 9901的值是多少。

输入格式

在一行中输入用空格隔开的两个整数A和B。

输出格式

输出一个整数，代表S mod 9901的值。

数据范围

0≤A,B≤5×10⁷

输入样例：

2 3

输出样例：

15

注意: A和B不会同时为0。

---

分析：

$设正整数X=p_1^{a_1}p_2^{a_2}...p_k^{a_k}，则X的约数之和为：$设正整数X=p1a1​​p2a2​​...pkak​​，则X的约数之和为：

$(1+p_1^1+p_1^2+...+p_1^{a_1})(1+p_2^1+p_2^2+...+p_2^{a_2})...(1+p_k^1+p_k^2+...+p_k^{a_k})$(1+p11​+p12​+...+p1a1​​)(1+p21​+p22​+...+p2a2​​)...(1+pk1​+pk2​+...+pkak​​)

$问题转化为，先对A^B进行分解质因数，接着对每个质因数进行等比数列求和。$问题转化为，先对AB进行分解质因数，接着对每个质因数进行等比数列求和。

$等比数列求和，可以利用求和公式+求逆元来直接计算。$等比数列求和，可以利用求和公式+求逆元来直接计算。

$这里采用分治的方法来计算。$这里采用分治的方法来计算。

$对于公比为q的等比数列，1,q,q^2,...,q^n，我们计算前k项的和，记sum(p,k)=1+p+...+p^{k-1}，$对于公比为q的等比数列，1,q,q2,...,qn，我们计算前k项的和，记sum(p,k)=1+p+...+pk−1，

$①、当k为偶数时，我们将:1,q,q^2,...,q^{k/2-1},q^{k/2},...,q^{k-1}，分为：$①、当k为偶数时，我们将:1,q,q2,...,qk/2−1,qk/2,...,qk−1，分为：

$\qquad 1,q,q^2,...,q^{k/2-1}和q^{k/2},...,q^{k-1}两部分，$1,q,q2,...,qk/2−1和qk/2,...,qk−1两部分，

$\qquad 则\sum_{i=0}^{k-1}p^i=\sum_{i=0}^{k/2-1}p^i+\sum_{i=k/2}^{k-1}p^i=\sum_{i=0}^{k/2-1}p^i+p^{k/2}\sum_{i=0}^{k/2-1}p^i=(1+p^{k/2})\sum_{i=0}^{k/2-1}p^i$则∑i=0k−1​pi=∑i=0k/2−1​pi+∑i=k/2k−1​pi=∑i=0k/2−1​pi+pk/2∑i=0k/2−1​pi=(1+pk/2)∑i=0k/2−1​pi

$\qquad 即：sum(p,k)=(1+p^{k/2})×sum(p,k/2)$即：sum(p,k)=(1+pk/2)×sum(p,k/2)

$②、当k为奇数时，则k-1为偶数，sum(p,k)=sum(p,k-1)+p^{k-1}。$②、当k为奇数时，则k−1为偶数，sum(p,k)=sum(p,k−1)+pk−1。

$③、特别地，k=1时，sum(p,1)=1。$③、特别地，k=1时，sum(p,1)=1。

代码：

#include<iostream>

using namespace std;

const int mod=9901;

int A,B;

int quick_pow(int a,int b)
{
    int res=1;
    a%=mod;
    while(b)
    {
        if(b&1) res=a*res%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

int sum(int p,int k)
{
    if(k==1) return 1;
    if(k%2==0) return (1+quick_pow(p,k/2))*sum(p,k/2)%mod;
    else if(k%2) return (sum(p,k-1)+quick_pow(p,k-1))%mod;
}

int main()
{
    cin>>A>>B;
    
    int res=1;
    for(int i=2;i<=A/i;i++)
    {
        int s=0;
        if(A%i==0)
        {
            while(A%i==0)
            {
                A/=i;
                s++;
            }
            res=res*sum(i,s*B+1)%mod;
        }
    }
    if(A>1) res=res*sum(A,B+1)%mod;
    if(A==0) res=0;
    
    cout<<res<<endl;
    
    return 0;
}