题目意思是,给出一个底数和他的幂,请计算这个数的所有因素之和。


下面对四个知识点进行梳理:

1、唯一分解定理:

定义:任何一个大于1的自然数N,如果N不为质数,那么N可以唯一分解成有限个质数的乘积A=p1^a1 * p2^a2 * p3^a3 *...* pn^an,这里p1<p2<p3......<pn均为质数,其中指数ai是正整数。这样的分解称为N的标准分解式。

由于 A = p1^a1 * p2^a2 * p3^a3 *...* pn^an.

所以A^B = p1^(a1*B) * p2^(a2*B) *...* pn^(an*B) 


2、递归二分(因为取模不能用数列求和公式):

sum = [1+p1+p1^2+...+p1^(a1*B)] * [1+p2+p2^2+...+p2^(a2*B)] *...*[1+pn+pn^2+...+pn^(an*B)]

例如:200 = 2^3 * 5^2 , sum(200) = [1 + 2 + 4 + 8] * [1 + 5 + 25]

转化:求等比数列1+pi+pi^2+pi^3+...+pi^n


若n为奇数,一共有偶数项,则:

1 + p + p^2 + p^3 +...+ p^n = (1+p^(n/2+1)) + p * (1+p^(n/2+1)) +...+ p^(n/2) * (1+p^(n/2+1))

= (1 + p + p^2 +...+ p^(n/2)) * (1 + p^(n/2+1))

如:1 + p + p^2 + p^3 + p^4 + p^5 = (1 + p + p^2) * (1 + p^3)


若n为偶数,一共有奇数项,则:

1 + p + p^2 + p^3 +...+ p^n = (1+p^(n/2+1)) + p * (1+p^(n/2+1)) +...+ p^(n/2-1) * (1+p^(n/2+1)) + p^(n/2) = (1 + p + p^2 +...+ p^(n/2-1)) * (1+p^(n/2+1)) + p^(n/2);

如:1 + p + p^2 + p^3 + p^4 = (1 + p) * (1 + p^3) + p^2


3、快速幂模:

把一个带幂的数拆分一下,幂为偶数的时候可以除一半,把底数多一个,奇数的时候先拆一个出来使幂变成偶数再计算。

可以看以前做过的题:BZOJ-1008 越狱(排列组合+快速幂)

blob.png

4、大数模运算:

(A*B)%C = ((A%C)*(B%C))%C


(A+B)%C = ((A%C)+(B%C))%C



所以,把上面的知识点拼凑起来写点代码:

StatusAccepted
Time16ms
Memory644kB
Length1011
LangG++
#include <iostream>
#include <cstdio>
using namespace std;
#define LL long long
#define MAX 10005
const int mod=9901;
int pri[MAX], cnt[MAX];
int a, b;
LL mmod(LL x, LL y){
    LL val=1;
    while(y){
        if(y&1)val=(val*x)%mod;
        x=(x*x)%mod;
        y/=2;
    }
    return val;
}
LL sum(LL p, LL n){
    if(n==0)return 1;
    if(n%2)
        return (sum(p, n/2) * (1+mmod(p, n/2+1))) % mod;
    else
        return (sum(p, n/2-1) * (1+mmod(p, n/2+1)) + mmod(p, n/2)) % mod;
}
int main()
{
    while(~scanf("%d%d", &a, &b)){
        int k=0;
        for(int i=2;i*i<=a;i++){
            if(a%i==0){
                pri[k++]=i;
                while(a%i==0){
                    cnt[k-1]++;
                    a/=i;
                }
            }
        }
        if(a!=1){
            pri[k]=a;
            cnt[k++]=1;
        }
        int ans=1;
        for(int i=0;i<k;i++){
            ans=ans*(sum(pri[i], cnt[i]*b)%mod)%mod;
        }
        printf("%d\n", ans);
    }
    return 0;
}