算法基础课笔记整理

1.试除法求约数

非常简单，不多赘述。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, t;
vector<int> ans;

void get_divisors(int x) {
    ans.clear();
    for (int i = 1; i <= x / i; i ++) {
        if (x % i == 0) {
            ans.push_back(i);
            if (x / i != i) ans.push_back(x / i);
        }
    }

    sort(ans.begin(), ans.end());

    return;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i ++) {
        cin >> t;
        get_divisors(t);
        for (int j = 0; j < ans.size(); j ++) cout << ans[j] << ' ';
        cout << endl;
    }

    return 0;
}

2.计算约数个数

根据唯一分解定理，我们知道： $x = p_1^{a_1} \times p_2^{a_2} \times … \times p_k^{a_k}$

所以其中任意选择一些质因数（每个 $p_i$ 最多选 $a_i$ 次）的乘积都是 $x$ 的约数，其中选择的质因数总数 $n$ 满足 $1 \leq n \leq \sum_{i=1}^k a_i$。

所以 $x$ 的约数个数就是 $(a_1 + 1) \times (a_2 + 1) \times … \times (a_k + 1)$

例题

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

输入格式

第一行包含整数 $n$。

接下来 $n$ 行，每行包含一个整数 $a_i$。

输出格式

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

数据范围

$1 \le n \le 100$,
$1 \le a_i \le 2 \times 10^9$

输入样例：

3
2
6
8

输出样例：

12

思路

根据上面说的，用一个哈希表记录每一个数的因数次数，最后按公式计算即可。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_map>

using namespace std;

const int mod = 1e9 + 7;

typedef long long LL;

int n, x;

LL ans = 1;

unordered_map<int, int> primes;

int main() {
    cin >> n;
    while (n --) {
        cin >> x;
        for (int i = 2; i <= x / i; i ++) {
            while (x % i == 0) {
                primes[i] ++;
                x /= i;
            }
        }
        if (x > 1) primes[x] ++;
    }

    for (pair<const int, int> prime : primes) {
        ans = ans * (prime.second + 1) % mod;
    }

    cout << ans << endl;

    return 0;
}

3.约数之和

计算公式： $(p_1^0 + p_1 ^ 1 + … + p_1^k) \times … \times (p_k^1 + p_k^2 + … + p_k^k)$

将其展开，则每一项都是 $x$ 的一个约数，加起来即为约数之和。

例题

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

输入格式

第一行包含整数 $n$。

接下来 $n$ 行，每行包含一个整数 $a_i$。

输出格式

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

数据范围

$1 \le n \le 100$,
$1 \le a_i \le 2 \times 10^9$

输入样例：

3
2
6
8

输出样例：

252

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_map>

using namespace std;

const int mod = 1e9 + 7;

typedef long long LL;

int n, x;

LL ans = 1;

unordered_map<int, int> primes;

int main() {
    cin >> n;
    while (n --) {
        cin >> x;
        for (int i = 2; i <= x / i; i ++) {
            while (x % i == 0) {
                x /= i;
                primes[i] ++;
            }
        }
        if (x > 1) primes[x] ++;
    }

    for (pair<const int, int> prime : primes) {
        LL p = prime.first, a = prime.second;
        LL t = 1;
        while (a --) t = (t * p + 1) % mod;
        ans = ans * t % mod;
    }

    cout << ans << endl;

    return 0;
}

注意这里求幂时用到了一个非常巧妙的方法。

假设某一时刻 $t = p_1^2 + p_1 ^ 1 + 1$

则全部乘上 $p$ 之后则为 $t = p_1^3 + p_1^2 + p_1^1 + 1$

4.最大公约数（gcd）

基本原理： $gcd(a, b) = gcd(b, a\mod b)$

证明：暂缺，有空补上

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

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

int n, a, b;

int main()
{
    cin >> n;
    while (n --) {
        cin >> a >> b;
        cout << gcd(a, b) << endl;
    }

    return 0;
}