约数之和

在普通的求a的约数之和的基础之上^b。

算法

约数之和的计算其他大佬已经写的很清楚了。a^b其每个约数出现的次数为a的约数出现次数乘上b。
此时如果(p^0 + ... + p^k)如果用for循环那么时间复杂度为a约数个数 * 1e7 在a约数个数超过
10时就很容易超时。(y总说过int中约数个数最多会有1500左右) 这里需要对求和计算做优化。
可用分治法优化(大佬说的很清楚 直接放出代码)

时间复杂度 O( c * log b )

C++ 代码

/*
 *求约数之和
 *  求约数 if a%i==0
 *  约数之和 pi为i约数 且出现了k次 连乘sum(pi^x) 0<=x<=k
 *  对于A^B 其约数个数扩大了B倍
 *  如果直接计算可能会超时 分治法优化
 *  sum(p,k) = p^0 + p^1 + ... + p^k
 *           = (p^0 + p^1 + ... + p^k/2 ) + ( p^k/2+1 + ... + p^k)
 *           = (p^k/2 + 1 ) * (p^0 + p^1 + ... + p^k/2 )
 *          如果 k%2==1 恰好可以分为两部分 sum(p,k) = sum(p,k/2)*(p^k/2+1) 当k==0时 返回0
 *          如果 k%2==0 可以先计算p^0 + ... + p^k-1  = sum(n,k-1) + p^k 或者用 1 + p* sum(n,k-1)
 *
 */
#include<cstdio>

typedef long long ll;

const int mod = 9901;

int qmi(int a, int p, int m)
{
    int res = 1;  
    while( p )
    {
        if( p&1 )   res = (ll) res * a % m;
        a = (ll)a * a % m;
        p >>= 1;
    }
    return res;
}

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

int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    if( !a )
    {
        printf("0\n");
    }
    else if( !b )
    {
        printf("1\n");
    }
    else
    {
        int s = 1;
        for( int i=2; i<=a/i; i++ )
        {//划分约数
            if( a%i==0 )
            {
                int cnt = 0; //记录约数乘积次数
                while( a%i==0 )
                {
                    cnt++;
                    a /= i;
                }
                s = (ll) s * sum(i,cnt*b) % mod; 
            }
        }
        if( a>1 )
        {
            s = (ll) s * sum(a,b) % mod;
        }
        printf("%lld\n",s);
    }
    return 0;
}