约数之和

首先了解几个定理：

约数个数定理

对一个大于1的整数$n$，$n$可以分解质因数为$\prod_{i=1}^{k}p_i^{a_i} = {p_1}^{a_1}·{p_2}^{a_2}···{p_k}^{a_k}$

则n的正约数的个数就是$f(n) = \prod_{i=1}^{k}a_i+1=(a_1+1)(a_2+1)···(a_k+1)$，这个很好证明，因为$p_1^{a_1}$的约数有$p_1^0,p_1^1,p_1^2...p_1^{a1}$，共$(a_1+1)$个，同理$p_k^{a_k}$的约数有$(a_k+1)$个

约数定理

$n$的$(a_1+1)(a_2+1)···(a_k+1)$个正约数的和为：

$$ (p_1^0+p_1^1+...+p_1^{a_1})(p_2^0+p_2^1+...p_2^{a_2})...(p_k^0+p_k^1+...p_k^{a_k}) $$

举个例子，$180 = 2^2*3^2*5^1$

约数个数：$(2+1)(2+1)(1+1) = 18$

约数和：$(1+2+4)(1+3+9)(1+5) = 546$

回到题目

对于这题来说，根据约数定理就有$A^B$的约数和为：

$$ (1+p_1^1+...+p_1^{Ba_1})(1+p_2^1+...p_2^{Ba_2})...(1+p_k^1+...p_k^{Ba_k}) $$

定义sum(n,k)为$p^0+p^1+...+p^k$，分成两部分的和变为$(p^0+...+p^{\frac{k}{2}})+(p^{\frac{k}{2}+1}+...p^k)$

后面的多项式提取$p^{\frac{k}{2}+1}$，变成$(p^0+...+p^{\frac{k}{2}})+p^{\frac{k}{2}+1} * (p^0+...p^{\frac{k}{2}})$

将两项合并$(1+p^{\frac{k}{2}+1}) * (p^0+...+p^{\frac{k}{2}})$，这个式子可以转化为$(1+p^{\frac{k}{2}}) * sum(p, \frac{k}{2})$

import java.util.Scanner;
public class Main {
    static int mod = 9901;
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int a = cin.nextInt();
        int b = cin.nextInt();
        int res = 1;
        for (int i = 2; i <= a; i++) {
            int s = 0;
            while (a % i == 0) {
                s++;
                a /= i;
            }
            if (s > 0)
                res = res * sum(i, s * b) % mod;
        }
        if (a == 0)
            res = 0;
        System.out.println(res);
    }
    static int sum(int p, int k) {
        if (k == 0)
            return 1;
        if (k % 2 == 0) 
            return (p % mod * sum(p, k - 1) + 1) % mod;
        return (1 + pow(p, k/2 + 1)) * sum(p, k >> 1) % mod;
    }
    private static int pow(int a, int k) {
        a %= mod;
        int res = 1;
        while (k != 0) {
            if ((k & 1) == 1)
                res = res * a % mod;
            a = a * a % mod;
            k >>= 1;
        }
        return res;
    }
}