因数（C++）

因数（C++）

因数

定义

qquad 在整数范围内，若 a a a 为整数， b b b 为非零整数，若存在整数 k k k，使得 a = k b a=kb a=kb，则称 b b b 是 a a a 的因数，记作 b ∣ a bspace | space a b ∣ a.

求所有因数

思路：

试除法

qquad 枚举每个可能的因数，进行试除。由于一个数的因数也是成对出现的，即如果 d ∣ n d|n d∣n ，则 n d ∣ n frac{n}{d}|n dn​∣n . 因此，只需要枚举 [ 1 , ⌊ n ⌋ ) [1,lfloor sqrt{n} rfloor ) [1,⌊n ​⌋) 之间的整数即可。

时间复杂度：

O ( n ) O(sqrt{n}) O(n ​)

代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> get_dividors(int n) {		//求n的所有因数，保存至res向量中vector<int> res;for (int i = 1; i <= n / i; i++)if (n % i == 0) {res.push_back(i);if (i != n / i)				//完全平方数，不能重复添加res.push_back(n / i);}sort(res.begin(), d());		//排序，时间复杂度小于sqrt(n)return res;
}
int main() {int x;cin >> x;auto res = get_dividors(x);for (auto t : res)	cout << t << " ";return 0;
}

分解质因数

思路：

qquad 本质上和求因数的方法一样：试除法。每次都用可以整除的因数除到不能再除为止，再枚举下一个数。最后作为除数的都是质数。

代码：

#include<iostream>
using namespace std;
int main() {int n, i = 2;cin >> n;while (n != 1) {int t = 0;while (n % i == 0) {	//满足这个条件的i一定是质数n /= i;t++;				//记录质因数i出现的次数}if (t == 1)printf("%d", i);if (t > 1)printf("%d^%d", i, t);if (t > 0 && n != 1)printf("*");i++;}return 0;
}

求因数个数

思路：

qquad 根据算术基本定理（唯一分解定理），任何一个大于1的自然数 N N N,如果 N N N 不为质数，那么 N N N 可以唯一分解成有限个质数的乘积 N = P 1 α 1 P 2 α 2 P 3 α 3 ⋯ P k α k N=P_1^{alpha_1}P_2^{alpha_2}P_3^{alpha_3} cdots P_k^{alpha_k} N=P1α1​​P2α2​​P3α3​​⋯Pkαk​​ ，这里 P 1 < P 2 < P 3 < ⋯ < P k P_1<P_2<P_3< cdots <P_k P1​<P2​<P3​<⋯<Pk​ 均为质数，其中指数 α i alpha_i αi​ 是正整数。

qquad N N N 的任何一个因数 d d d 的形式为：
d = P 1 β 1 P 2 β 2 P 3 β 3 ⋯ P n β k , 其中 0 ≤ β i ≤ α i d=P_1^{beta_1}P_2^{beta_2}P_3^{beta_3}cdots P_n^{beta_k},其中0lebeta_ilealpha_i d=P1β1​​P2β2​​P3β3​​⋯Pnβk​​,其中0≤βi​≤αi​
qquad 相当于在N的质因数里面选，故总因数个数为：
c n t = ( α 1 + 1 ) ( α 2 + 1 ) ⋯ ( α k + 1 ) cnt = (alpha_1+1)(alpha_2+1) cdots (alpha_k+1) cnt=(α1​+1)(α2​+1)⋯(αk​+1)
举个例子：

qquad 18 = 2 1 ∗ 3 2 18 = 2^1*3^2 18=21∗32，那么18的因数个数为 ( 1 + 1 ) ∗ ( 2 + 1 ) = 6 (1+1)*(2+1)=6 (1+1)∗(2+1)=6 个。显然18的因数有： 1 ， 2 ， 3 ， 6 ， 9 ， 18 1，2，3，6，9，18 1，2，3，6，9，18，确实为6个。

小tip：

qquad int 范围内的数字的因数个数最大为1536个。

时间复杂度：

O ( n ) O(sqrt n) O(n ​)

代码：

#include <iostream>
using namespace std;
int cnt_dividors(int n) {int res = 1;int p = 2;					//枚举每个数while (n != 1) {int a = 0;				//质因数个数while (n % p == 0) {	//成立时p一定为质数n /= p;a++;}res *= (a + 1);p++;}return res;
}
int main() {int x;cin >> x;auto cnt = cnt_dividors(x);cout << cnt;return 0;
}

求因数之和

思路：

公式为：
s u m = ( P 1 0 + P 1 1 + ⋯ + P 1 α 1 ) ( P 2 0 + P 2 1 + ⋯ + P 2 α 2 ) ⋯ ( P k 0 + P k 1 + ⋯ + P k α k ) sum=(P_1^0+P_1^1+cdots +P_1^{alpha_1})(P_2^0+P_2^1+cdots+P_2^{alpha_2})cdots(P_k^0+P_k^1+cdots+P_k^{alpha_k}) sum=(P10​+P11​+⋯+P1α1​​)(P20​+P21​+⋯+P2α2​​)⋯(Pk0​+Pk1​+⋯+Pkαk​​)
即：
s u m = ∏ i = 1 k ∑ j = 0 α k P i j sum = prodlimits_{i=1}^ksumlimits_{j=0}^{alpha_k}P_i^j sum=i=1∏k​j=0∑αk​​Pij​
qquad 将此公式展开可得到一个总共 c n t = ( α 1 + 1 ) ( α 2 + 1 ) ⋯ ( α k + 1 ) cnt = (alpha_1+1)(alpha_2+1)cdots(alpha_k+1) cnt=(α1​+1)(α2​+1)⋯(αk​+1) 项的多项式，其中每项的形式为 P 1 β 1 P 2 β 2 P 3 β 3 ⋯ P n β k , 其中 0 ≤ β i ≤ α i P_1^{beta_1}P_2^{beta_2}P_3^{beta_3}cdots P_n^{beta_k},其中0lebeta_ilealpha_i P1β1​​P2β2​​P3β3​​⋯Pnβk​​,其中0≤βi​≤αi​ ，恰好符合上一章节所讲内容。故这里的 s u m sum sum 为所求的所有因数之和。

举个例子：

qquad 18 = 2 1 × 3 2 18 = 2^1 times 3^2 18=21×32，那么18的因数之和为 ( 2 0 + 2 1 ) ∗ ( 3 0 + 3 1 + 3 2 ) = 39 (2^0+2^1)*(3^0+3^1+3^2)=39 (20+21)∗(30+31+32)=39 个。显然18的因数之和： 1 + 2 + 3 + 6 + 9 + 18 = 39 1+2+3+6+9+18=39 1+2+3+6+9+18=39，确实为39。

关键代码分析：

1.

qquad 对于求 P 1 0 + P 1 1 + ⋯ + P 1 α 1 P_1^0+P_1^1+cdots +P_1^{alpha_1} P10​+P11​+⋯+P1α1​​ 这样一个式子，采用下面这种方法求解：

LL t = 1;
while (a--)	t = t * p + 1;		//p为质因数，a为指数

qquad 第一次： t = p + 1 t = p + 1 t=p+1

qquad 第二次： t = ( p + 1 ) × p + 1 = p 2 + p + 1 t=(p+1)times p+1=p^2+p+1 t=(p+1)×p+1=p2+p+1

qquad 第三次： t = ( p 2 + p + 1 ) × p + 1 = p 3 + p 2 + p + 1 t=(p^2+p+1)times p+1=p^3+p^2+p+1 t=(p2+p+1)×p+1=p3+p2+p+1

qquad 第 α 1 alpha_1 α1​次： t = p 1 0 + p 1 1 + ⋯ + p 1 α 1 t=p_1^0+p_1^1+cdots +p_1^{alpha_1} t=p10​+p11​+⋯+p1α1​​

qquad 如此来看，这样计算的时间复杂度为 O ( α 1 ) O(alpha_1) O(α1​)。

2.

qquad 不建议采用快速幂求解，理由如下：

qquad 对于 P 1 α 1 P_1^{alpha_1} P1α1​​ 来说，快速幂求解的时间复杂度为 O ( l o g α 1 ) O(logalpha_1) O(logα1​)，那么这整个式子的时间复杂度就为 O ( α 1 l o g α 1 ) O(alpha_1logalpha_1) O(α1​logα1​)，效率更低了。

3.

qquad 可以选择采用快速幂+等比数列求和公式来求解：
P 1 0 + P 1 1 + ⋯ + P 1 α 1 = P 1 α 1 + 1 − P 1 0 P 1 − 1 = P 1 α 1 + 1 − 1 P 1 − 1 P_1^0+P_1^1+cdots +P_1^{alpha_1}=frac{P_1^{alpha_1+1}-P_1^0}{P_1-1}=frac{P_1^{alpha_1+1}-1}{P_1-1} P10​+P11​+⋯+P1α1​​=P1​−1P1α1​+1​−P10​​=P1​−1P1α1​+1​−1​
qquad 这样的话时间复杂度为 O ( l o g α 1 ) O(logalpha_1) O(logα1​)。

时间复杂度：

qquad 采用 1 的话，总计算量为 k × α ktimes alpha k×α，其中 k k k 为自然数 N N N 的质因数个数。

代码：

LL sum_dividors(int n) {LL res = 1;int p = 2;					//枚举每个数while (n != 1) {LL t = 1;while (n % p == 0) {	//成立时p一定为质数n /= p;t = t * p + 1;}res *= t;p++;}return res;
}

最大公因数

欧几里得算法（辗转相除法）

公式：

qquad 用gcd(a,b)表示a与b的最大公因数，则：
g c d ( a , b ) = g c d ( b , a m o d b ) gcd(a,b) = gcd(b,aspace modspace b) gcd(a,b)=gcd(b,a mod b)
qquad 当 b = 0 b=0 b=0 时， g c d ( a , 0 ) = a gcd(a,0)=a gcd(a,0)=a.

举个例子：

qquad 当我们求 36 和 24 的最大公因数时：
g c d ( 36 , 24 ) = g c d ( 24 , 12 ) = g c d ( 12 , 0 ) = 12 gcd(36,24)=gcd(24,12)=gcd(12,0)=12 gcd(36,24)=gcd(24,12)=gcd(12,0)=12

证明：

qquad 设 a = b k + c a=bk+c a=bk+c，显然有 c = a m o d b c=aspace mod space b c=a mod b.

1. 设 d ∣ a , d ∣ b dspace |space a,dspace |space b d ∣ a,d ∣ b，则 c = a − b k c=a-bk c=a−bk 可得出：
c d = a d − b d k ∈ Z frac{c}{d}=frac{a}{d}-frac{b}{d}k space in Z dc​=da​−db​k ∈Z
qquad 因此 d ∣ c d space | space c d ∣ c.

qquad 故：若 d d d 为 a a a 和 b b b 的公因数，则 d d d 也是 b b b 和 a m o d b aspace modspace b a mod b 的公因数。

2. 反过来：

qquad 设 d ∣ b , d ∣ ( a m o d b ) dspace |space b,dspace |space (aspace modspace b) d ∣ b,d ∣ (a mod b)，则同理可得到：
a m o d b d + b d k = a d ∈ Z frac{aspace modspace b}{d}+frac{b}{d}k=frac{a}{d} space in Z da mod b​+db​k=da​ ∈Z
qquad 因此 d ∣ a d space | space a d ∣ a.

qquad 故：若 d d d 为 b b b 和 a m o d b aspace modspace b a mod b 的公因数，则 d d d 也是 a a a 和 b b b 的因数。

综上所述， a 和  b 的公因数 ⇔ b 和  a m o d b 的公因数 space aspace和space bspace的公因数Leftrightarrow b space和space aspace modspace b的公因数  a 和 b 的公因数⇔b 和 a mod b的公因数，即 g c d ( a , b ) = g c d ( b , a m o d b ) gcd(a,b) = gcd(b,aspace modspace b) gcd(a,b)=gcd(b,a mod b).

另：

qquad 我们也可以得到以下结论：

qquad 求两个数 a 和 b 的所有公因数，即求他们最大公因数的所有因数。

代码：

1.递归写法

int gcd(int a, int b) {return b ? gcd(b, a % b) : a;
}

2.循环写法

int gcd(int a, int b) {while (b) {int temp = b;b = a % b;a = temp;}return a;
}

3.多个数字求最大公因数

int mul_gcd(vector<int> vec) {int res = vec[0];for (auto t : vec)	res = gcd(res, t);return res;
}