MENU

约数之和

February 19, 2019 • Read: 4737 • 算法阅读设置

首先了解几个定理:

约数个数定理

对一个大于 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;
  • }
  • }
Last Modified: April 25, 2019
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment

已有 1 条评论
  1. 小庄 小庄

    $p^k/2+1 * (p^0+p^1+...+p^k/2) 这个多项式比原式多了一项好像。$