NYOJ 928 小M的因子和（數論）

小M在上課時有些得意忘形，老師想出道題目難住他。小M聽說是求因子和，還是非常得意，但是看完題目是求A的B次方的因子和，有些手足無措了，你能解決這個問題嗎？

2 3

15

分析：對A進行質因數分解，假設A = (p1^a1) * (p2^a2)*……*(pk^ak),假設A的因子和為sum，

則sum=(1 + p1 + p1^2 + ……+p1^a1)*(1+p2+p2^2 + ……+p2^a2)*……*(1+pk+pk^2+……+pk^ak)，把這個式子展開之後.每一項剛好是A的因子。

所以求A^B的因子和時，只需把ai 改為ai*b，然後再求解即可。求得時候因為次方比較大，要用分治和快速冪來求。

#include 
#include 
const int mod = 9901;

int Pow(int a, int n) {  //快速冪求a^n
    int res = 1;
    a %= mod;
    while(n) {
        if(n&1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

int get_sum(int a, int n) {  //求(1 + a + a^2 + …… + a^n)
    if(n == 0) return 1;
    if(n&1) return get_sum(a, n / 2) * (Pow(a, (n / 2 + 1)) + 1) % mod;
    else return (get_sum(a, n / 2 - 1) * (Pow(a, n / 2) + 1) + Pow(a, n)) % mod;
}

int main() {
    int a, b;
    while(~scanf("%d%d", &a, &b)) {
        int ans = 1;
        int m = (int)sqrt(a + 0.5);
        for(int i = 2; i <= m; ++i) {
            if(a % i == 0) {
                int k = 0;
                while(a % i == 0) {
                    k++;
                    a /= i;
                }
                ans = ans * get_sum(i, k * b) % mod;
            }
        }
        if(a > 1) ans = ans * get_sum(a, b) % mod;
        printf("%d\n", ans);
    }
    return 0;
}