数论-约数

因数，也称为约数（英语：Divisor）是一个常见的数学名词，用于描述自然数 \(a\) 和自然数 \(b\) 之间存在的整除关系，即 \(b\)可以被\(a\) 整除。这里我们称 \(b\) 是 \(a\) 的倍数，\(a\) 是 \(b\) 的因数或因子。

试除法求约数

​ 试除法的思路很简单和求质数一样，求一个数\(n\)的所有约束，可以枚举从 \(1 \sim n\) 的所有数，把它记录下来。这里有一个优化，如果 \(d|n\) 那么 \(\frac{n}{d} | n\) ，所以约束也是成对出现的，只要枚举 \(\frac{n} {d}\) 和 \(d\) 之中较小的那个即可。只需要使 \(d <= \frac{n} {d}\) 即只需要枚举到 \(d <= \sqrt{n}\)。

【问题描述】

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

【输入格式】

第一行包含整数 \(n\)。

接下来 \(i\) 行，每行包含一个整数 \(a_i\)。

【输出格式】

输出共 \(n\) 行，其中第 \(i\) 行输出第 \(i\) 个整数 \(a_i\) 的所有约数。

【输入样例】

2

6

8

【输出样例】

1 2 3 6
1 2 4 8

#include<bits/stdc++.h>
using namespace std;

vector<int> div(int n) {
    vector<int> ans;
    
    for (int i = 1; i <= n / i; i ++) {
        if (n % i == 0) {
            ans.push_back(i);
            if (i != n / i) ans.push_back(n / i);  // 注意边界情况，有可能出现 n/i == i的情况导致重复加入数值
        }
    }    
    sort(ans.begin(), ans.end());
    
    return ans;
}


int main()
{
    int n;
    cin >> n;
    while (n --) {
        int x; cin >> x;
        auto ans = div(x);
        for (auto t : ans) cout << t << ' ';
        cout << endl;
    }
    
    
    return 0;
}

约数的个数

自然数 N 的因数个数以 \(d(n)\) 表示。若 \(N\) 唯一分解为

\({\displaystyle N=p_{1}^{a_{1}}\times p_{2}^{a_{2}}\times p_{3}^{a_{3}}\times \cdots \times p_{n}^{a_{n}}=\prod _{i=1}^{n}p_{i}^{k_{i}}}\),

则 \({\displaystyle d(N)=(a_{1}+1)\times (a_{2}+1)\times (a_{3}+1)\times \cdots \times (a_{n}+1)=\prod _{i=1}^{n}\left(a_{i}+1\right)}\)

例如 \(2646=2\times 3^{3}\times 7^{2}\)，则其正因数个数 \(d(2646)=(1+1)\times (3+1)\times (2+1)=24\)。

【问题描述】

给定 \(n\) 个正整数 \(a_i\)，请你输出这些数的乘积的约数个数，答案对 \(10^9 + 7\) 取模。

【输入格式】

第一行包含整数 \(n\)。

接下来 \(i\) 行，每行包含一个整数 \(a_i\)。

【输出格式】

输出一个整数，表示所给正整数的乘积的约数个数，答案对 \(10^9 + 7\) 取模。

【输入样例】

3

2

6

8

【输出样例】

12

#include<bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
typedef long long ll;
map<int, int> p;

int main()
{
    int n, x;
    cin >> n;
    while (n --) {
        cin >> x;
        for (int i = 2; i <= x / i; i ++) {
            if (x % i == 0) {
                while (x % i == 0) x /= i, p[i] ++;
            }
        }
        if (x > 1) p[x] ++;
    }
    
    ll ans = 1;
    for (auto t : p) ans = ans * (t.second + 1) % mod; // define的时候mod不是整型，是double不能取模，const int mod = 1e9 + 7比较保险。
    cout << ans;
    
    return 0;
}

给定任意一个数\(n\)，求其约数的个数。上题相当于求 \(96\) 的约数的个数。

约数之和

自然数 \(N\) 的正因数和，以因数函数 \({\displaystyle \sigma (N)}\)表示。由质因数分解而得。

若 \(N\) 唯一分解为 \({\displaystyle N=p_{1}^{a_{1}}\times p_{2}^{a_{2}}\times p_{3}^{a_{3}}\times \cdots \times p_{n}^{a_{n}}=\prod _{i=1}^{n}p_{i}^{k_{i}}}\), 则 \({\displaystyle \sigma (N)=\prod _{i=1}^{n}\left(\sum _{j=0}^{a_{i}}p_{i}^{j}\right)}\)

再由等比级数求和公式可知，上式亦可写成：

\({\displaystyle {\begin{aligned}\sigma (N)&={\frac {p_{1}^{a_{1}+1}-1}{p_{1}-1}}\times {\frac {p_{2}^{a_{2}+1}-1}{p_{2}-1}}\times \cdots \times {\frac {p_{n}^{a_{n}+1}-1}{p_{n}-1}}&\end{aligned}}}\)

例如\({\displaystyle 2646=2\times 3^{3}\times 7^{2}}\)，则其正因数之和

\({\displaystyle {\begin{aligned}\sigma (2646)&=(1+2)\times (1+3+9+27)\times (1+7+49)\\&={\frac {2^{2}-1}{2-1}}\times {\frac {3^{4}-1}{3-1}}\times {\frac {7^{3}-1}{7-1}}\\&=3\times 40\times 57\\&=6840\end{aligned}}}\)

【问题描述】

给定 \(n\) 个正整数 \(a_i\)，请你输出这些数的乘积的约数之和，答案对 \(10^9 + 7\) 取模。

【输入格式】

第一行包含整数 \(n\)。

接下来 \(i\) 行，每行包含一个整数 \(a_i\)。

【输出格式】

输出一个整数，表示所给正整数的乘积的约数之和，答案对 \(10^9 + 7\) 取模。

【输入样例】

3

2

6

8

【输出样例】

252

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int mod = 1e9 + 7;

int main()
{
    int n;
    map<int, int> p;
    cin >> n;
    while (n --) {
        int x; cin >> x;
        for (int i = 2; i <= x / i; i ++) {
            if (x % i == 0) {
                while (x % i == 0) x /= i, p[i] ++;
            }
        }
        if (x > 1) p[x] ++;
    }
    
    ll ans = 1;
    for (auto t : p) {
        int a = t.first, b = t.second;
        ll k = 1;
        while (b --) k = (k * a + 1) % mod;
        ans = ans * k % mod;
    }
    
    cout << ans;
    
    return 0;
}

代码前半部分与之前几乎一样，后半部分很像秦九韶算法，主要是用于计算等比数列和。

例如 \(1+3+3^2+3^3\) 可以写成 \(3(3(3+1)+1)+1\) ，CPU计算加法比乘法快，可以算的快一点也可以采用快速幂计算等比数列前\(n\)项和

最大公约数

求最大公约数一般采用欧几里得算法，欧几里得算法的核心其实是\(gcd(a, b) = gcd(b, a\ mod\ b)\)下面进行证明

1. 对\(a\ mod \ b\)进行变换

   \[\begin{align*}
   a\ mod\ b &= a - \left \lfloor \frac{a}{b} \right \rfloor \times b\\
   &=a - c\times b
   \end{align*}
   \]

2. 证明对于\(a\)和\(b\)的任意公约数\(k\)，都是\(b\)和\(a\ mod\ b\)的公约数
   是\(b\)的公约数，同时也是\(a-c\times b\) 的公约数

3. 证明对于\(b\)和\(a\ mod\ b\)的任意公约数\(m\)，都是\(a\)和\(b\)的公约数

   即证明\(m\)是\(a\)的公约数，\(m\)可以整除\(a\ mod\ b\)，则\(m\)可以整除\(a-c\times b\)所以\(m\)可以整除\(a\)

综上所述，集合\(cd(a, b)\)等于集合\(cd(b, a\ mod\ b)\)，则\(gcd(a, b) = gcd(b, a\ mod\ b)\)，该过程的实现如下

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

顺便一提，最小公倍数的求法\(lcm(a, b) = \frac{a\times b} {gcd(a, b)}\)

int lcm(a, b) {
	return a / gcd(a, b) * b; // 不要写成a*b/gcd(a, b)可能会溢出，先除会让数小一些
}