数学知识（一）

约数

设$a$为一个非零整数，$b$是一个整数，如果存在一个整数$q$ ，使得 $b=a*q$，那么$b$可被$a$整除，记作 $a|b$ ，$b$是$a$的倍数，$a$是$b$的约数

性质

1、如果$a|b$且$b|c$，那么$a|c$

2、$a|b$且$a|c$，对任意的整数$x$和$y$，有$a|(b*x+c*y)$

3、$a|b$等价于$(a*m)|(b*m)$，m不为零

4、设整数$x$ 和 $y$满足下式$a*x + b * y =1$，且$a|n$，$b|n$，那么$(a*b)|n$

算术基本定理

任何一个大于1的自然数 N,如果

N不为质数，那么N可以唯一分解成有限个质数的乘积

$$N = p_1^c1p_2^c2...p_m^cm$$

其中$ci$都是正整数

试除法求整数x的正约数集合

时间复杂度$O（n*sqrt(n)）$

vector<int> res;
int x;
for (int i = 1; i<= x / i; i ++)
    if (x % i == 0) {
        res.emplace_back(i);
        if(i != x / i) res.emplace_back(x/i);
    }

倍数法求整数x的正约数集合

设有$d|n$。

d = 1，d为1~n所有数的约数，数量为n；

d = 2，d为2，4，6，8……的约数，数量为$\frac{n}{2}$;

d = 3，d为3，6，9……的约数，数量为$\frac{n}{3}$;

……

d = n，数量为$\frac{n}{n}$;

共有

$$n*(1+\frac{1}{2}+\frac{1}{3}+……+\frac{1}{n}) = n*logn$$

时间复杂度为O(n*logn)

vector<int> res[N];
for (int i = 1 ; i<= n; i ++)
    for ( int j = 1; j <= n/ i; j ++) res[i*j].emplace_back(i);

约数个数

基于算术基本定理

$$N = p_1^{c1}p_2^{c2}...p_m^{cm}$$

N的约数

$$d = p_1^b1p_2^b2...p_m^bm$$

$bi$可以取 [0,ci]，共ci+1种取法，约数个数总数为

$$\sum_{i=1}^n(ci+1)$$

https://www.acwing.com/problem/content/description/872/

代码

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

const int N = 110, mod = 1e9+7;
int t,n;
int main(){
    cin>>t;
    unordered_map<int,int> q;
    long long ans = 1;
    while (t--){
        cin>>n;
        for (int i= 2; i <= n / i; i ++)
            if (n % i == 0){
                while ( n % i == 0){
                    n /= i;q[i]++;
                }
            }
            if(n > 1) q[n]++;
    }
    for (auto i : q) ans = ans*(i.second + 1) % mod;
    cout<<ans<<'\n';
}

约数之和

约数和为

$$(1 + p_1 +p_1^2 + ...+p_1^{c1})*(1+p_2+p_2^2+...+p_2^{c2}) + ...+(1+p_m+p_m^2+...+p_m^{cm})$$

N的约数d可以分解成

$$d = p_1^{b1}p_2^{b2}...p_m^{bm}$$

约数和公式得到的每一项都是d的形式

倍增法求约数和

vector<int> res[N];
for (int i = 1 ; i<= n; i ++)
    for ( int j = 1; j <= n/ i; j ++) res[i*j].emplace_back(i);
for (int i = 1; i<= n; i++){
    int ans = 0;
	for (int j = 0; j < res[i].size(); j ++) ans += res[i][j];
    cout<<ans<<'\n';
}

https://www.acwing.com/problem/content/description/873/

代码

#include <iostream>
#include <unordered_map>
using namespace std;

const int N = 110, mod = 1e9+7;
int t,n;
int main(){
    cin>>t;
    unordered_map<int,int> q;
    long long ans = 1;
    while (t--){
        cin>>n;
        for (int i= 2; i <= n / i; i ++)
            if (n % i == 0){
                while ( n % i == 0){
                    n /= i;q[i]++;
                }
            }
            if(n > 1) q[n]++;
    }
    for (auto i : q) {
        auto p = i.first, s = i.second;
        long long cnt = 1;
        while (s--) cnt = (cnt * p + 1) % mod;
        ans = ans * cnt % mod;
    }
    cout<<ans<<'\n';
}

GCD LCM

由算术基本定理可知，整数$A=p_1^{a_1}+p_2^{a_2}+p_3^{a_3}+...+p_m^{a_m}$,整数$B=p_1^{b_1}+p_2^{b_2}+p_3^{b_3}+...+p_m^{b_m}$

对于$A$和$B$的约数$d=p_1^{0-min(a_1,b_1)}+p_2^{0-min(a_2,b_2)}+p_3^{0-min(a_3,b_3)}+...+p_m^{0-min(a_m,b_m)}$

则$A$和$B$的最大公约数$gcd(A,B)=p_1^{min(a_1,b_1)}+p_2^{min(a_2,b_2)}+p_3^{min(a_3,b_3)}+...+p_m^{min(a_m,b_m)}$

$A$和$B$的最小公倍数

$lcm(A,B)=p_1^{max(a_1,b_1)}+p_2^{max(a_2,b_2)}+p_3^{max(a_3,b_3)}+...+p_m^{max(a_m,b_m)}$

证得$A*B=gcd(A,B)*lcm(A,B)$

如何直观求GCD——辗转相除法

$$gcd(a,b) = gcd(a\pmod b,b)$$

设$r(a,b)$为$a$，$b$所有公因数的集合，有$gcd(a,b)=max(r(a,b))$
要证$gcd(a,b) = gcd(a,a-b)$，只需证$r(a,b) = r(a,a-b)$

根据整除的性质$d|b$且$d|c$，那么对任意的整数$x$,$y$，有$d|(x*b+y*c)$

$a,b$的公因数是$a,a-b$的公因数，$a,a-b,a$的公因数是$a,b$的公因数

证得$r(a,b)=r(a,a-b)$，则$gcd(a,b) = gcd(a,a-b)$