数学知识：约数（试除法求约数、求约数个数和约数之和、最大公约数）_综合

ACWing 869. 试除法求约数

给定n个正整数ai，对于每个整数ai,请你按照从小到大的顺序输出它的所有约数。

输入格式
第一行包含整数n。
接下来n行，每行包含一个整数ai。

输出格式
输出共n行，其中第 i 行输出第 i 个整数ai的所有约数。

数据范围
1≤n≤100,
2≤ai≤2?10⁹
输入样例：
2
6
8
输出样例：
1 2 3 6
1 2 4 8

试除法优化：
约数成对出现，枚举一对中较小者即可。

Code：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;vector<int> get_divisors(int n)
{
    vector<int> res;for(int i = 1; i <= n / i; i ++){
    if(n % i == 0){
    res.push_back(i);if(i != n / i) //n可能是i的平方，此时只输出一个ires.push_back(n / 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 t: res)  {
    cout << t << ' ';}cout << endl;}return 0;
}

ACWing 870. 约数个数

给定n个正整数ai，请你输出这些数的乘积的约数个数，答案对10⁹+7取模。

输入格式
第一行包含整数n。
接下来n行，每行包含一个整数ai。

输出格式
输出一个整数，表示所给正整数的乘积的约数个数，答案需对10⁹+7取模。

数据范围
1≤n≤100,
1≤ai≤2?10⁹
输入样例：
3
2
6
8
输出样例：
12

求解约数个数的思路：
一个数分解质因数后可表示为 N = p1^α1 p2^α2…… pk^αk（pi是质因数的底数即质因子，αi是指数）
N的任意一个约数可表示为n = p1^β1 p2^β2…… pk^βk（0 ≤ βi ≤ αi, i = 1,2……,k）
n指数的选法不同就会产生不同的约数，所以β1、β2…… βk 的选法就等于约数个数。
由乘法定理，β1有α1 + 1种选法，β2有α2 + 1种选法……βk有αk + 1种选法，则约数个数为 (α1 + 1)(α2 + 1)……(αk + 1)

对于本题，采用map存放 primes 数组，将底数与指数一一映射。枚举每个数的质因数，并把他们写入到 primes 数组中，即每个数分解质因数，对应质因子指数累加。将乘积的质因数求解完毕后，采用上述的公式，求约数个数即可。

Code：

#include <iostream>
#include <algorithm>
#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 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 prime : primes)  res = res * (prime.second + 1) % mod;cout << res << endl;return 0;
}

ACWing 871. 约数之和

给定n个正整数ai，请你输出这些数的乘积的约数之和，答案对109+7取模。

输入格式
第一行包含整数n。
接下来n行，每行包含一个整数ai。

输出格式
输出一个整数，表示所给正整数的乘积的约数之和，答案需对10⁹+7取模。

数据范围
1≤n≤100,
1≤ai≤2?10⁹
输入样例：
3
2
6
8
输出样例：
252

求解约数之和的思路：
约数之和为(p1⁰+p1¹+……+p1^α1)(p2⁰+p2¹+……+p2^α2)……（pk⁰+pk¹+……+pk^αk)
证明：从每一括号内选一个值相乘就构成了一个约数，对应有 (α1 + 1)(α2 + 1)……(αk + 1)个约数，由乘法原理，约数之和就可以表示为(p1⁰+p1¹+……+p1^α1)(p2⁰+p2¹+……+p2^α2)……（pk⁰+pk¹+……+pk^αk)。
(p⁰+p¹+……+p^α)的简便求法，初始化 t = 1, 循环 α 次 t = p * t + 1，最终的 t 值就是该式的结果。

Code:

#include <iostream>
#include <algorithm>
#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 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 prime : primes){
    int p = prime.first, a = prime.second;LL t = 1;while(a --)t  = (p * t + 1) % mod;res = res * t % mod;}cout << res << endl;return 0;
}

AcWing 872. 最大公约数

给定n对正整数ai,bi，请你求出每对数的最大公约数。

输入格式
第一行包含整数n。
接下来n行，每行包含一个整数对ai,bi。

输出格式
输出共n行，每行输出一个整数对的最大公约数。

数据范围
1≤n≤105,
1≤ai,bi≤2?10⁹
输入样例：
2
3 6
4 6
输出样例：
3
2

最大公约数思路：
定理：一个数能整除x, 也能整除y, 那么它也一定能整除x和y的线性组合（即ax+by, a、b为任意整数），则gcd(a,b) = gcd(b, a % b), a%b可以看做a - c*b(其中c=[a/b])，由上述定理可知，等号左边和右边的最大公约数相同。

Code:

#include <iostream>
#include <algorithm>
using namespace std;int gcd(int a, int 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;
}