第四讲 数学知识——约数

AcWing 869. 试除法求约数

时间复杂度 \(O(n\sqrt a)\)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> res;
int n, a;
int main()
{
    cin >> n;
    while (n--) {
        res.clear();
        cin >> a;
        for (int i = 1; i <= a / i; ++i) {
            if (a % i == 0) {
                if (a / i == i) res.push_back(i);
                else res.push_back(i), res.push_back(a / i);
            }
        }
        sort(res.begin(), res.end());
        for (int it : res)
            cout << it << " ";
        cout << endl;
    }
    return 0;
}

AcWing 870. 约数个数

\(N=\prod\limits_{i=1}^{k}p_i^{d_i}\)

公式 \(\prod\limits_{i=1}^k(d_i+1)\)

怎么理解公式呢？可以分两种情况。

我们先设 \(b=\prod\limits_{j=1}^{i-1}(d_j+1)\)

情况一 \(i > 1\)

用乘法分配律得 \(b \cdot d_i + b\)

其中 \(b \cdot d_i\) 是用乘法原理新组成的约数，\(b\) 是旧的约数。

情况二 \(i=1\)

约数个数就是 \(d^i+1\)

\(d_i\) 新的，而 \(1\) 是每个因数必有的 \(1\)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int MOD = 1e9 + 7;
int n, a;
unordered_map<int, int> d;
int main()
{
    cin >> n;
    while (n--) {
        cin >> a;
        for (int i = 2; i <= a / i; ++i) {
            while (a % i == 0) {
                ++d[i];
                a /= i;
            }
        }
        if (a > 1) ++d[a];
    }
    long long ans = 1;
    for (auto it : d) {
        ans = ans * (it.second + 1) % MOD;
    }
    printf("%lld\n", ans);
    return 0;
}

AcWing 871. 约数之和

\(N=\prod\limits_{i=1}^{k}p_i^{d_i}\)

公式 \(\prod\limits_{i=1}^k\sum\limits_{j=0}^{d_i}p_{i}^{j}\)

证明很简单用乘法分配律展开就是了。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int MOD = 1e9 + 7;
int n, a;
unordered_map<int, int> d;
int main() {
    cin >> n;
    while (n--) {
        cin >> a;
        for (int i = 2; i <= a / i; ++i) {
            while (a % i == 0) {
                ++d[i];
                a /= i;
            }
        }
        if (a > 1) ++d[a];
    }
    long long ans = 1;
    for (auto it : d) {
        long long t = 0, tt = 1;
        for (int i = 0; i <= it.second; ++i)
            t = (t + tt) % MOD, tt = it.first * tt % MOD;
        ans = ans * t % MOD;
    }
    printf("%d\n", ans);
    return 0;
}

AcWing 872. 最大公约数

热知识：一般 \(\gcd(a,b)\) 都写成 \((a,b)\)

公式 \((a,b)=(b,a \mod b)\)

证明：

\(\begin{aligned}a \mod b&=a-\lfloor{\frac{a}{b}}\rfloor\cdot b\\&=a-x\cdot b \end{aligned}\)

我们设 \(d=(a,b)\)

那么 \(d \mid a,d\mid b,d\mid a+b, d\mid ax+by\)

所以 \((a,b)=(b,a-\lfloor{\frac{a}{b}}\rfloor\cdot b)=(b,a\mod b)\)

证毕

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int n, a, b;
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
int main() {
    cin >> n;
    while (n--) {
        cin >> a >> b;
        cout << gcd(a, b) << endl;
    }
    return 0;
}