简单的数学知识

一些简单的数学知识

质数 约数

质数

质数即为因子只有自己和1的数，合数有多个因子包括且不限于自己和1

求质数的方法有很多

试除法

试除法是比较简单的一个方法

只需要循环从1到n之间的所有数字

时间复杂度为 $O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>

using namespace std;

void solve()
{
    int cot;
    cin >> cot;
    for(int i = 2;i < cot;i ++)
    {
        if(cot % i == 0)
        {
            puts("No");
            return ;
        }
    }
    puts("Yes");
}

int main()
{
    int t = 1;
    cin >>  t;
    while(t --)
    {
        solve();
    }
    return 0;
}

埃氏筛

但是试除法很慢，所以需要一种$O(n * log(n))$的写法

对于一个数n来说，他的最大的因子是$\sqrt{x}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>

using namespace std;

void solve()
{
    int cot;
    cin >> cot;
    if(cot == 1)
    {
        puts("No");
        return ;
    }
    for(int i = 2;i <= cot / i;i ++)
    {
        if(cot % i == 0)
        {
            puts("No");
            return ;
        }
    }
    puts("Yes");
}

int main()
{
    int t = 1;
    cin >>  t;
    while(t --)
    {
        solve();
    }
    return 0;
}

欧氏筛

如果对于从1到n的质数，那么使用埃氏筛该如何写呢

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>

using namespace std;
const int N = 1e6 + 10;
int f[N];

void solve()
{
	int n;
	cin >> n;
	for(int i = 2;i <= n;i ++)
	{
	    for(int j = 2;j <= n / j;j ++)
	    {
	        f[i * j] = 1;
	    }
	}
	for(int i = 1; i <= n;i ++)
	{
	    cout << f[i] << ' ';
	}
}

int main()
{
	solve();
	return 0;
}

但是这种写法有可能被一些数据卡掉，所以就需要线性筛即欧氏筛

为什么线性筛会比埃氏筛快呢，埃氏筛中在计算时进行了很多余的计算 例如 6 它会被 i = 2 和 i = 3 计算两次

线性筛会在出现这种情况的时候及时退出，不在计算节省了时间，线性筛使用了空间换时间优化了埃氏筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<iostream>

using namespace std;
const int N = 1e6 + 10;
int f[N], p[N], idx;

void solve()
{
	int n;
	cin >> n;
	for(int i = 2;i <= n;i ++)
	{
	    if(!f[i]) p[idx ++] = i;
	    for(int j = 0;j < idx && i * p[j] <= n;j ++)
	    {
	        if(i * p[j] <= n) f[i * p[j]] = 1;
	        if(i % p[j] == 0) break;
	    }
	}
	cout << idx << '\n';
}

int main()
{
	solve();
	return 0;
}

约数

对于求每个数的约数，同样可以使用试除法来完成

那么有没有更快的方法呢

对于一个数n，它有一个因子为a，那么一定存在另一个因子b，得到 a * b = n

并且a和b的最大值为$\sqrt{n}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>

using namespace std;

void solve()
{
    int n;
    cin >> n;
    for(int i = 1;i <= n / i;i ++)
    {
        if(n % i == 0) cout << i << ' ' << n / i << ' ';
    }
    puts("");
}

int main()
{
    int t = 1;
    cin >> t;
    while(t --)
    solve();
    return 0;
}

约数个数的计算

给出n个数，求相乘之后的因子数量

对于他们的乘积all的因子有

$all = a_1^a * a_2^b….*a_n^t$

对于每个因子都有对应的次方数，即每个因子可以选择对应的次方数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
#include<map>

const int mod = 1e9 + 7;

using namespace std;

void solve()
{
    int n;
    cin >> n;
    map<int,int> ma;
    for(int i = 0; i < n;i ++)
    {
        int cot;
        cin >> cot;
        for(int j = 2;j <= cot / j;j ++)
        {
            while(cot % j == 0)
            {
                ma[j] ++;
                cot /= j;
            }
        }
        if(cot > 1) ma[cot] ++;
    }
    int ans = 1;
    
    for(auto &[u,v] : ma)
    {
        ans = 1ll * ans * (v + 1) % mod;    
    }
    cout << ans << '\n';
}

int main()
{
    solve();
    return 0;
}

约数之和的计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>
#include<map>

using namespace std;

const int mod = 1e9 + 7;

void solve()
{
    int n;
    cin >> n;
    
    map<int,int> ma;
    
    for(int i = 0;i < n;i ++)
    {
        int cot;
        cin >> cot;
        for(int j = 2;j <= cot / j;j ++)
        {
            while(cot % j == 0)
            {
                ma[j] ++;
                cot /= j;
            }
        }
        if(cot > 1) ma[cot] ++;
    }
    
    long long ans = 1;
    
    for(auto &[u,v] : ma)
    {
        long long t = 1;
        while(v --) t = (t * u + 1) % mod;
        ans = (ans * t) % mod;
    }
    cout << ans << endl;
}
int main()
{
    solve();
    return 0;
}

对于其乘积为all，$all = a_1 * a_2 * a_3 … * a_n$

即其中所所有的因子的次方和相加再将所有的次方和相乘

$(p_1^1+p_1^2+p_1^3+…)(….)(p_n^1+p_n^2+p_n^3+…)$

每个相乘出来即可得到结果

欧几里得

有两个数 a 和 b，求出 a 和 b的最大公约数

辗转相除法可求得也叫欧几里得（gcd）

首先假设$gcd(a,b) = c$,即a和b的最大公因数是c
$$
a = c * a_1, b = c * b_1;
a / b = k……t; a / b 的商是k，余数是t;
$$

$$
ca_1 = ck*b_1 + t
$$

$$
整理得 c(a_1 + k * b_1) = tc(a_1 + k * b_1) = t
$$

t从数值上可得为 a % b,且$c(a_1 + k * b_1) = t$ 即c为t的因子

可证得$gcd(a,b) = gcd(b,c*a - c * k * b)$=>gcd(a,b) = gcd(b,a % b);

辗转相除即为a%b的相互模取

为什么是 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>

using namespace std;

int gcd(int a, int b)
{
    int r = a % b;
    while(r)
    {
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

int main()
{
    int n;
    cin >> n;
    while(n --)
    {
        int a, b;
        cin >> a >> b;
        cout << gcd(a,b) << '\n';
    }
    return 0;
}

扩展欧几里得算法

扩展欧几里得可以求解$a * x +b *y = gcd(a,b)$,求出一个 x 和 y 的结果且x和y不为零

有裴蜀定理可得一定有解，且x和y不为零，当且仅当 $ax + by = 1$时，a和b互质

证明：如果a和b不为质数即$a = a_1 * c,b = b_1 * c$,c为gcd(a,b)，可得$c*(a_1 + b_1) = 1$，当前仅当c为1时成立

扩展欧几里得推导

以gcd为基础
$$
a * x + b * y = d \newline
b * x_1 + (a - \lfloor a /b\rfloor * b) *y_1 = d \newline
=> b * x_1 + (a - \lfloor a /b\rfloor * b) *y_1 = a * x + b * y \newline
=> ecgcd(a,b,x,y) = exgcd(b,a( mod )b,y,x)
$$
当递归到gcd中b为0时，有$a_n * x = d$,此时可由gcd得知$a_n = d$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>

using namespace std;

int exgcd(int a,int b,int &x,int &y)
{
    if(!b)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    
    return d;
}

void solve()
{
    int n;
    cin >> n;
    while(n --)
    {
        int a, b, x, y;
        cin >> a >> b;
        exgcd(a, b, x, y);
        cout << x << ' ' << y << '\n';
    }
}

int main()
{
    solve();
    return 0;
}

费马小定理

给n对数字 a 和 p，p为质数

求解 a 模 p 的乘法逆元

即$a / b\equiv a * x \pmod{m}$ => $b * x \equiv 1 \pmod{m}$

可通过费马小定理得出

证明费马小定理

对于一个质数，求解他的关于m的乘法逆元

有 $$\prod_{i=1}^{n} a_i$$ = $\prod_{i=1}^{p - 1}(a_i * k) \pmod{p}$
$$
\because (a_i,p)=1,(a_i * k,p)=1 \
a^{p-1} * \prod_{i=1}^{p-1}a_i = \prod_{i=1}^{p-1}a_i \pmod{p} \
\ => a^{p-1} = 1 \pmod{p}
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>

using namespace std;
#define ll long long

ll qpow(int a,int b,int p)
{
    ll ans = 1;
    while(b)
    {
        if(b&1) ans = ans * a % p;
        a = 1ll * a * a % p;
        b >>= 1;
    }
    return ans;
}

int main()
{
    int n;
    cin >> n;
    while(n --)
    {
        int a, b;
        cin >> a >> b;
        if(a % b) cout << qpow(a, b - 2, b) << '\n';
        else puts("impossible");
    }
    return 0;
}
数学 > Arithmetic
#数学
简单的数学知识
http://example.com/2024/03/26/数学类知识/
作者
smg
发布于
2024年3月26日
许可协议