约数
约数的定义
若整数 \(n\) 除以整数 \(d\) 的余数为 \(0\)，即 \(d\) 能整除 \(n\)，则称 \(d\) 是 \(n\) 的约数，\(n\) 是 \(d\) 的倍数，记为 \(d|n\)。
算数基本定理的推论
正约数集合
在算数基本定理中，若正整数 \(N\) 被唯一分解为 \(N = p_1^{c_1}p_2^{c_2}...p_m^{c_m}\)，其中 \(c_i\) 都是正整数，\(p_i\) 都是质数，且满足 $p_1 < p_2 < ... < p_m $，则 \(N\) 的正约数集合可以写作：
\[\lbrace p_1^{c_1}p_2^{c_2}...p_m^{c_m} \rbrace,其中 0 \le b_i \le c_i \]正约数个数
\[(c_1 + 1) * (c_2 + 1) * ... * (c_m + 1) = \prod_{i=1}^{m}(c_i + 1) \]此处 \(1\) 代表质数 \(p_i\) 的 \(0\) 次方。
正约数之和
\[(1 + p_1 + p_1^2 + ... + p_1^{c_1}) * ... * (1 + p_m + p_m^2 + ... + p_m^{c_m}) = \prod_{i=1}^{m}(\sum_{j=0}^{c_i}(p_i)^j) \]上式按照乘法多项式展开之后的每一项都是 \(N\) 的一个约数。
一、试除法求约数
如果 \(d > \sqrt{N}\) 是 \(N\) 的约数，那么 \(N/d \le \sqrt{N}\) 也是 \(N\) 的约数。换言之，约数总是成对出现的（对于完全平方的数字，\(\sqrt{N}\) 会单独出现一次）。
因此，只需扫描 \(1\) 到 \(\sqrt{N}\) 之间的数字，尝试能否整除 \(N\)，若能整除，则 \(N/d\) 也是 \(N\) 的约数。
时间复杂度：\(O(\sqrt{N})\)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void get_divisors(int n)
{
// 用于存储约数
vector<int> res;
// 枚举从 1 到 sqrt(n) 的数
for (int i = 1; i <= n / i; i ++ )
// 如果 i 是 n 的约数
if (n % i == 0) {
// 将 i 存起来
res.push_back(i);
// 如果不是完全平方数，则将 n/i 也存起来
if (i != n / i) res.push_back(n / i);
}
// 排序约数数组
sort(res.begin(), res.end());
for (auto i : res) cout << i << ' ';
puts("");
}
int main()
{
int n;
cin >> n;
while (n -- ) {
int a;
cin >> a;
get_divisors(a);
}
return 0;
}
二、约数个数
利用算数基本定理的推论
时间复杂度：\(O(\sqrt{N})\)
#include <iostream>
#include <unordered_map>
using namespace std;
typedef long long LL;
const int MOD = 1e9 + 7;
int main()
{
int n;
cin >> n;
// 采用哈希表存储每一个质因子对应出现的次数
unordered_map<int, int> primes;
while (n -- ) {
int a;
cin >> a;
// 筛质数
for (int i = 2; i <= a / i; i ++ )
while (a % i == 0) {
a /= i;
primes[i] ++;
}
if (a > 1) primes[a] ++;
}
LL res = 1;
// 代公式
for (auto prime : primes) res = res * (prime.second + 1) % MOD;
cout << res << endl;
return 0;
}
三、约数之和
时间复杂度：\(O(\sqrt{N})\)
#include <iostream>
#include <unordered_map>
using namespace std;
const int MOD = 1e9 + 7;
typedef long long LL;
int main()
{
int n;
cin >> n;
unordered_map<int, int> primes;
while (n -- ) {
int a;
cin >> a;
for (int i = 2; i <= a / i; i ++ )
while (a % i == 0) {
a /= i;
primes[i] ++;
}
if (a > 1) primes[a] ++;
}
LL res = 1;
for (auto prime : primes) {
int p = prime.first, c = prime.second;
LL t = 1;
while (c -- ) t = (t * p + 1) % MOD;
res = res * t % MOD;
}
cout << res << endl;
return 0;
}
四、最大公约数
欧几里得算法
\[\forall a,b \in \mathbb{N}, b \neq 0, gcd(a,b)=gcd(b, a \bmod b) \]证明：
- 若 $ a \le b$，则 \(gcd(b, a \bmod b) = gcd(b,a) = gcd(a,b)\)，显然成立。
- 若 \(a \ge b\)，不妨设 \(a = q * b + r\)，其中 \(0 \le r < b\)。显然 \(r = a \bmod b\)。对于 \(a,b\) 的任意公约数 \(d\)，因为 \(d|a\), \(d|q * b\)，故 \(d|(a-qb)\) ，即 \(d|r\)，因此 \(d\) 也是 \(b,r\) 的公约数。反之亦成立。故 \(a,b\) 的公约数集合与 \(b, a \bmod b\) 的公约数集合相同。于是他们的最大公约数自然相等。
时间复杂度：\(O(\log(a+b))\)
#include <iostream>
using namespace std;
int gcd(int a, int b)
{
// 0可以被任何数整除
return b ? gcd(b, a % b) : a;
}
int main()
{
int n;
cin >> n;
while (n -- ) {
int a, b;
cin >> a >> b;
cout << gcd(a, b) << endl;
}
return 0;
}
也可调用STL的__gcd()函数：
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
while (n -- ) {
int a, b;
cin >> a >> b;
cout << __gcd(a, b) << endl;
}
return 0;
}
欧几里得算法是最常用的求最大公约数的算法。不过，因为高精度除法（取模）不容易实现，需要做高精度运算时，可考虑用更相减损数代替欧几里得算法。