首先了解几个定理:
约数个数定理
对一个大于 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;
- }
- }
$p^k/2+1 * (p^0+p^1+...+p^k/2) 这个多项式比原式多了一项好像。$