约数定理（约数个数定理，约束和定理）

约数个数定理可以计算出一个数约数的个数

约数个数定理

对于一个大于1正整数n可以分解质因数： $_math_inline$f(n)=\prod^k_{i=1}{p_i}^{a_i}={p_1}^{a_1}\cdot{p_2}^{a_2}\cdot...\cdot{p_k}^{a_k}$math_inline_$

则n的正约数的个数就是 $_math_inline$f(n)=\prod^k_{i=1}(a_i+1)=(a_1+1)+(a_2+1)..(a_k+1)$math_inline_$ 。

其中 $_math_inline$a_1、a_2、a_3...a_k$math_inline_$ 是 $_math_inline$p_1、p_2、p_3，p_k$math_inline_$ 的指数。

定理简证

首先同上，n可以分解质因数 $_math_inline$n={p_1}^{a_1}\times{p_2}^{a_2}\times ... \times{p_k}^{a_k}$math_inline_$ ,

由约数定义可知 $_math_inline${p_1}^{a_1}$math_inline_$ 的约数有: $_math_inline${p_1}^0, {p_1}^1, {p_1}^2......{p_1}^{a_1}$math_inline_$ ，共 $_math_inline$(a_1+1)$math_inline_$ 个;同理 $_math_inline${p_2}^{a_2}$math_inline_$ 的约数有 $_math_inline$(a_2+1)$math_inline_$ 个…… $_math_inline${p_k}^{a_k}$math_inline_$ 的约数有 $_math_inline$(a_k+1)$math_inline_$ 个。

故根据乘法原理：n的约数的个数就是 $_math_inline$(a_1+1)(a_2+1)(a_3+1)…(a_k+1)$math_inline_$ 。

例

例：正整数378000共有多少个正约数？

解：将378000分解质因数 $_math_inline$378000=2^4×3^3×5^3×7^1$math_inline_$

由约数个数定理可知378000共有正约数 $_math_inline$(4+1)×(3+1)×(3+1)×(1+1)=160$math_inline_$ 个。

实现

 1int f1(int n) {
 2    int r = (int) sqrt(1.0 * n);
 3    int sum = 0;
 4    if (r * r == n) {
 5        sum++;
 6        r--;
 7    }
 8    for (int i = 1; i <= r; i++)
 9        if (n % i == 0) {
10            sum += 2;
11        }
12    cout << sum << endl;
13}
14
15// 稍快于f1
16int f2(int n){
17    int s = 1, r;
18    for (int i = 2; i * i <= n; i++) {
19        r = 0;
20        while (n % i == 0) {
21            r++;
22            n /= i;
23        }
24        if (r > 0) {
25            r++;
26            s *= r;
27        }
28    }
29    if (n > 1)
30        s *= 2;
31    cout << s << endl;
32}
33
34ll f3(ll n) {
35    ll res=1;
36    for(ll i=2;i*i<=n;i++){
37        ll k=0;
38        while(n%i == 0){
39            n = n/i;
40            k++;
41        }
42        if(k) res *= (k+1);
43    }
44    if(n != 1) res=res*2;
45    if(res==1){
46        if(n==1) return 1;
47        else return 2;
48    }
49    cout << res << endl;
50}

约数和定理

对于一个大于1正整数n可以分解质因数： $_math_inline$n={p_1}^{a_1}\cdot{p_2}^{a_2}\cdot...\cdot{p_k}^{a_k}$math_inline_$

则由约数个数定理可知n的正约数有 $_math_inline$(a_i+1)(a_2+1)(a_3+1)$math_inline_$ 个，那么n的 $_math_inline$(a_i+1)(a_2+1)(a_3+1)$math_inline_$ 个正约数的和为

定理证明

若n可以分解质因数： $_math_inline$n=p_1^{a_1}*p_2^{a_2}*p_3^{a_3}*...*p_k^{a_k}$math_inline_$

可知 $_math_inline$p_1^{a_1}$math_inline_$ 的约数有： $_math_inline$p_1^0,p_1^1,p_1^2,...,p_1^{a_1}$math_inline_$

….

同理可知， $_math_inline$p_k^{a_k}$math_inline_$ 的约数有： $_math_inline$p_k^0,p_k^1,p_k^2,...,p_k^{a_k}$math_inline_$

实际上n的约数是在 $_math_inline$p_1^{a_1}、p_2^{a_2}、p_3^{a_3}、...、p_k^{a_k}$math_inline_$ 每一个的约数中分别挑一个相乘得来，可知共有 $_math_inline$(a_1+1)(a_2+1)(a_3+1)...(a_k+1)$math_inline_$ 种挑法，即约数的个数。

由乘法原理可知它们的和为

例

例：正整数360的所有正约数的和是多少？

解：

将360分解质因数可得 $_math_inline$360=2^3 * 3^2 * 5^1$math_inline_$

由约数和定理可知，360所有正约数的和为

可知360的约数有：

则它们的和为：

实现

 1ll qpow(ll x, ll y) {
 2    ll res = 1;
 3    while (y) {
 4        if (y & 1) res *= x;
 5        x *= x;
 6        y >>= 1;
 7    }
 8    return res;
 9}
10
11ll getsum(ll n) {//返回n的约数和是多少.
12    ll res = 1;
13    for (ll i = 2; i * i <= n; i++) {
14        ll k = 0;
15        while (n % i == 0) {
16            n = n / i;
17            k++;
18        }
19        res *= ((1 - qpow(i, k + 1)) / (1 - i));
20    }    //用等比数列公式(快速幂)算.
21    if (n != 1) res *= (1 + n);
22    cout << res << endl;
23}

题目

求正约数应用例题hihocoder – 1284

直接暴力肯定不行, 所以想到求他们的约数, 则n的约数*m的约数/GCD(n,m)的约数就是答案. 求约数用以上定理.

 1ll getnum(ll n) { //得到a的约数个数.
 2    ll res = 1;
 3    for (ll i = 2; i * i <= n; i++) {
 4        ll k = 0;
 5        while (n % i == 0) {
 6            n = n / i;
 7            k++;
 8        }
 9        if (k) res *= (k + 1);
10    }
11    if (n != 1) res = res * 2;   //最后一个素数.
12    if (res == 1) {    //本身就是素数或1.
13        if (n == 1) return 1;
14        else return 2;
15    }
16    return res;
17}
18
19void solve(ll n, ll m) {
20    ll k = __gcd(m, n);
21    ll num1 = getnum(n);
22    ll num2 = getnum(m);
23    ll num3 = getnum(k);
24    ll t = __gcd(num3, num1 * num2);
25    printf("%lld %lld\n", 1ll * num1 * num2 / t, 1ll * num3 / t);
26}