简单的数学知识

一些简单的数学知识

质数 约数

质数

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

求质数的方法有很多

试除法

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

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

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

#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;
}
C++

埃氏筛

但是试除法很慢，所以需要一种$$的写法

对于一个数n来说，他的最大的因子是$$

#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;
}
C++

欧氏筛

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

#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;
}
C++

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

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

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

#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;
}
C++

约数

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

那么有没有更快的方法呢

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

并且a和b的最大值为$$

#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;
}
C++

约数个数的计算

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

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

$$

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

#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;
}
C++

约数之和的计算

#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;
}
C++

对于其乘积为all，$$

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

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

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

欧几里得

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

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

首先假设$$,即a和b的最大公因数是c
$$

$$
ca_1 = ck*b_1 + t
$$

$$

t从数值上可得为 a % b,且$$ 即c为t的因子

可证得$$=>gcd(a,b) = gcd(b,a % b);

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

为什么是

#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;
}
C++

扩展欧几里得算法

扩展欧几里得可以求解$$,求出一个 x 和 y 的结果且x和y不为零

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

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

扩展欧几里得推导

以gcd为基础
$$
当递归到gcd中b为0时，有$$,此时可由gcd得知$$

#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;
}
C++

费马小定理

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

求解 a 模 p 的乘法逆元

即$$ => $$

可通过费马小定理得出

证明费马小定理

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

有 $$ = $$
$$

#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;
}
C++