约数之和

首先了解几个定理：

约数个数定理

对一个大于 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;
    }
}