文章目录
一、约数
二、试除法求约数
题目描述
输入样例
2
2
6
输出样例
1 2 3 6
1 2 4 8
具体实现
1. 实现思路
与试除法判断质数是相同的道理。
当 d可以整除 n 时，显然，n / d 也可以整除 n 。例如，当 n = 12 时，3 是 12的约数，4 也是 12 的约数，他们是成对存在的。
因此，在我们枚举的过程中，只需要枚举其中较小的一个即可，时间复杂度是O(n)
- 用 vector 存储一个数的所有约数。
2. 实现代码
#include <bits/stdc++.h> using namespace std; vector<int> get_divisors(int x) { vector<int> res; for (int i = 1; i <= x / i; i ++ ) { if (x % i == 0) { res.push_back(i); //判断边界情况 if (i != x / i) { res.push_back(x / i); } } } //对约数排序 sort(res.begin(), res.end()); return res; } int main() { int n; cin >> n; while (n -- ) { int x; cin >> x; //自动对应数据类型 auto res = get_divisors(x); for (auto x : res) { cout << x << ' '; } cout << endl; } return 0; }
三、约数个数
输入样例
3
2
6
8
输出样例
12
具体实现
1. 实现思路
一个数的约数是由这个数的几个质因子相乘得到的。
例如：12 的质因子有 2，3。12 的约数有：1，2，3，4，6，12。
约数 1 是由 0 个 2， 0 个 3 相乘得到的。
约数 2 是由 1 个 2， 0 个 3 相乘得到的。
约数 3 是由 0 个 2， 1 个3 相乘得到的。
约数 4 是由 2 个 2， 0 个3 相乘得到的。
约数 6 是由 1 个 2， 1 个3 相乘得到的。
约数 12 是由 2 个 2， 1 个 3相乘得到的。
- 由上述公式，我们求解出每一个约数后，套用公式即可。
2. 实现代码
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 110, mod = 1e9 + 7; int main() { int n; cin >> n; //第一个存储质因子的底数 //第二个存储质因子的指数 unordered_map<int, int> primes; while (n -- ) { int x; cin >> x; for (int i = 2; i <= x / i; i ++ ) { while (x % i == 0) { x /= i; primes[i] ++ ; } } if (x > 1) { primes[x] ++ ; } } LL res = 1; for (auto p : primes) { res = res * (p.second + 1) % mod; } cout << res << endl; return 0; }
四、约数之和
输入样例
3
2
6
8
输出样例
252
具体实现
1. 实现思路
- 关于约数之和，有如下计算公式：
2. 实现代码
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 110, mod = 1e9 + 7; int main() { int n; cin >> n; //第一个存储质因子的底数 //第二个存储质因子的指数 unordered_map<int, int> primes; while (n -- ) { int x; cin >> x; for (int i = 2; i <= x / i; i ++ ) { while (x % i == 0) { x /= i; primes[i] ++ ; } } if (x > 1) { primes[x] ++ ; } } LL res = 1; for (auto p : primes) { LL a = p.first, b = p.second; LL t = 1; while (b -- ) { t = (t * a + 1) % mod; } res = res * t % mod; } cout << res << endl; return 0; }
五、最大公约数（欧几里得算法、辗转相除法）
输入样例
2
3 6
4 6
输出样例
3
2
具体实现
1. 实现思路
最大公约数（Greatest Common Divisor）指两个或多个整数共有约数中最大的一个。也称最大公因数、最大公因子，a， b 的最大公约数记为（a，b），同样的，a，b，c 的最大公约数记为（a，b，c），多个整数的最大公约数也有同样的记号。
如果 d 可以整除 a，同时，d 也可以整除 b，那么，d 就可以整除 ax+by。
便可以得到如下公式：（a，b）=（b，a mod b）。
代码模板如下所示：
int gcd(int a, int b) { //返回a和b的最大公约数 return b ? gcd(b, a % b) : a; }
2. 实现代码
#include <bits/stdc++.h> using namespace std; int gcd(int a, int b) { //返回a和b的最大公约数 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; }
