[置顶] 数学知识学习(持续更新)

wangping · 2022-01-12 23:42:37 · 个人记录

数学知识学习(持续更新)

Ⅰ 质数

⒈ 试除法

⑴ 判定素数

时间复杂度：\Theta(\sqrt{n})

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

bool isPrime(int x)
{
    if (x < 2)
        return false;
    for (int i = 2; i <= x / i; i ++ )
    {
        if (x % i == 0)
            return false;
    }
    return true;
}

int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int x;
        cin >> x;
        if (isPrime(x))
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    return 0;
}

⑵ 分解质因数

时间复杂度：\Theta(\log n)与\Theta(\sqrt{n})之间

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

void isPrime(int x)
{
    for (int i = 2; i <= x / i; i ++ )
    {
        if (x % i == 0)
        {
            int s = 0;
            while (x % i == 0)
                x /= i, ++s;
            cout << i << " " << s << "\n";
        }
    }
    if (x > 1)
        cout << x << " " << 1 << "\n";
    cout << "\n";
}

int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int x;
        cin >> x;
        isPrime(x);
    }
    return 0;
}

⒉ 埃氏筛

原理：

将 1 ~ n 排成一行，从第1个开始，在每个数上向后把这个数的倍数全部筛掉，这样就可以只剩下质数了。

时间复杂度：\Theta(n\log \log n)

附：一般，\log \log n 会忽略不计，也就是说，时间复杂度近似 \Theta(n)。但是，真正能做到 \Theta(n) 的算法是下一个算法——线性筛。

Code - 模板

int primes[N], cnt;
bool st[N];

void ass(int n)//埃氏筛模板
{
    for (int i = 2; i <= n; ++i)
    {
        if (!st[i])
        {
            primes[cnt++] = n;
            for (int j = i + i; j <= n; j += i)
                st[j] = true;
        }
    }
}

Code - 用法

int main()
{
    int n;
    cin >> n;
    ass(n);
    cout << cnt;
    return 0;
}

记

我们发现这里面似乎会对某些数标记了很多次其为合数。有没有什么办法省掉无意义的步骤呢？请看下一个算法！

⒊ 线性筛法（埃氏筛优化）

优化方式：

我们在上一个算法中提到埃氏筛会对某些数标记了很多次其为合数，如果能让每个合数都只被标记一次，那么时间复杂度就可以降到 \Theta(n)了。

时间复杂度：\Theta(n)

Code - 模板

const int N = 1000010;
int primes[N], cnt;
bool st[N];

void xxs(int n)//线性筛模板
{
    for (int i = 2; i <= n; ++i)
    {
        if (!st[i])
            primes[cnt++] = i;
        for (int j = 0; primes[j] <= n / i; ++j)
        {
            st[primes[j]*i] = true;
            if (i % primes[j] == 0)
                break;
        }
    }
}

Code - 用法

int main()
{
    int n;
    cin >> n;
    xxs(n);
    cout << cnt;
    return 0;
}

分析

对于代码 if(i%primes[j]==0)break;，n 只会被最小的质因子筛掉。 证明如下：

这里，我们分两种情况来讨论。

1. i%primes[j]==0，则 primes[j] 一定是 i 的最小质因子，primes[j] 也一定是 primes[j]*i 的最小质因子。
2. i%primes[j]!=0，则 primes[j] 一定小于 i 的所有质因子，primes[j] 也一定是 primes[j]*i 的最小质因子。

证毕!

Ⅱ 约数

⒈ 试除法求约数

时间复杂度：\Theta(\sqrt{n})

Code - 模板

vector<int> get_divisors(int n)\\试除法求约数模板
{
    vector<int> res;
    for (int i = 1; i <= n / i; ++i)
    {
        if (n % i == 0)
        {
            res.push_back(i);
            if (i != n / i)
                res.push_back(n / i);
        }
    }
    sort(res.begin(), res.end());\\不必要时可以不加
    return res;
}

注意：这个模板求的约数是以 vector 的类型返回的，所以，在使用时，要小心。具体使用方法看下面的用法代码。

Code - 用法

int x;
cin >> x;
auto res = get_divisors(x);
for (auto t : res)
    cout << t << " ";

⒉ 约数个数与约数和专题

0 注

本小节的内容部分摘自这里

⑴ 基本定理

算术基本定理：设 n={p_1}^{r_1}{p_2}^{r_2}{p_3}^{r_3}\cdots{p_k}^{r_k}

约数个数公式：d(n)=(r_1+1)\times(r_2+1)\times(r_3+1)\times\cdots\times(r_k+1)

约数和公式：\sigma(n)=\prod\limits_{i=1}^k\left(\sum\limits_{j=0}^{r_i}{p_i}^{j}\right)

⑵ 求单个数的约数个数

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

/**
 * 功能：计算约数个数
 * @param n
 * @return
 */
LL getDivisorCount(LL x)
{
    unordered_map<int, int> primes; //key:质数 value:个数
    //求质数因子
    for (int i = 2; i <= x / i; i++)
        while (x % i == 0) x /= i, primes[i]++; //primes[i]表示质数i因子的个数+1
    //如果还有质数，那就加上
    if (x > 1) primes[x]++;
    //公式大法
    LL res = 1;
    for (auto p: primes) res = res * (p.second + 1);
    return res;
}

LL res;

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cout << i << " " << getDivisorCount(i) << endl;
    return 0;
}

⑶ 求数字连乘积的约数个数

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;

int main()
{
    int n;
    cin >> n;
    unordered_map<int, int> primes;
    while (n--)
    {
        int x;
        cin >> x;
        for (int i = 2; i <= x / i; ++i)
        {
            while (x % i == 0)
            {
                x /= i;
                ++primes[i];
            }
        }
        if (x > 1)
            ++primes[x];
    }
    long long res = 1;
    for (auto prime : primes)
        res = res * (prime.second + 1) % mod;
    cout << res;
}

⑷ 求单个数字的约数和

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
/**
 * 功能：计算约数之和
 * @param n
 * @return
 */
LL getSumOfDivisors(LL x)
{
    //拆出所有质数因子及质数因子个数
    unordered_map<int, int> primes;
    for (int i = 2; i <= x / i; i++)
        while (x % i == 0)
        {
            x /= i;
            primes[i]++;
        }
    if (x > 1) primes[x]++;
    //计算约数个数
    LL res = 1;
    for (auto p : primes)
    {
        LL a = p.first, b = p.second;
        LL t = 1;
        while (b--) t = (t * a + 1);
        res = res * t;
    }
    return res;
}
LL res;
int main()
{
    int n;
    cin >> n;
    cout<<getSumOfDivisors(n) << endl;
    return 0;
}

⑸ 求数字连乘积的约数和

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
unordered_map<int, int> primes;

int main()
{
    int n, x;
    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]++;
    }
    ll res = 1;
    for (auto p : primes)
    {
        ll a = p.first, b = p.second;
        ll t = 1;
        while (b--)
            t = (t * a + 1) % mod;
        res = res * t % mod;
    }
    cout << res << endl;
    return 0;
}

⑹ 筛法求区间内的约数个数与约数和

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
/**
 * 功能：线性筛出约数个数与约数和
 * Tag:模板，约数个数，约数和
 */
const int N = 1e6 + 10;
int n;
int primes[N];      //质数数组
int idx;            //质数数组下标游标
bool st[N];         //是否已被筛出
int d[N];           //约数个数数组
int sigma[N];       //约数和数组
void get_divisor(int n)
{
    //积性函数的出发值
    d[1] = sigma[1] = 1;
    for (int i = 2; i <= n; i++)  //倍数
    {
        if (!st[i])primes[++idx] = i, d[i] = 2, sigma[i] = i + 1;
        for (int j = 1; i * primes[j] <= n & j <= idx; j++)
        {
            st[i * primes[j]] = true;
            d[i * primes[j]] = d[i] << 1;
            sigma[i * primes[j]] = sigma[i] * (primes[j] + 1);
            if (i % primes[j] == 0)
            {
                d[i * primes[j]] -= d[i / primes[j]];
                sigma[i * primes[j]] -= primes[j] * sigma[i / primes[j]];
                break;
            }
        }
    }
}
LL res;
int main()
{
    cin >> n;
    //开始筛约数个数，约数和
    get_divisor(n);
    //输出约数个数和
    for (int i = 1; i <= n; i++) res += d[i];
    cout << res << endl;
    return 0;
}

⑺辗转相除法求最大公约数

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

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

int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", gcd(a, b));
    }
    return 0;
}

Ⅲ 欧拉函数

定义

在数论，对正整数 n，欧拉函数是小于等于 n 的正整数中与 n 互质的数的数目。

定理

设 n={p_1}^{r_1}{p_2}^{r_2}{p_3}^{r_3}\cdots{p_k}^{r_k}

那么 \varphi(n) = n\times\left(1 - \dfrac{1}{p_1}\right) \times \left(1 - \dfrac{1}{p_2}\right) \times\cdots\times\left(1 - \dfrac{1}{p_k}\right)

Code - 求单个数的欧拉函数

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

int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        int a;
        cin >> a;
        int res = a;
        for (int i = 2; i <= a / i; ++i)
        {
            if (a % i == 0)
            {
                res = res / i * (i - 1);
                while (a % i == 0)
                    a /= i;
            }
        }
        if (a > 1)
            res = res / a * (a - 1);
        cout << res << endl;
    }
    return 0;
}

求 1 到 n 的欧拉函数之和（欧拉筛）

分析

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
int n, phi[N], prime[N], cnt;
bool st[N];

long long get_euler(int x)
{
    phi[1] = 1;
    for (int i = 2; i <= x; i++)
    {
        if (!st[i])
        {
            prime[cnt++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; prime[j] <= x / i; j++)
        {
            st[i * prime[j]] = true;
            if (i % prime[j] == 0)
            {
                phi[i * prime[j]] = prime[j] * phi[i];
                break;
            }
            else
                phi[i * prime[j]] = (prime[j] - 1) * phi[i];
        }
    }
    long long res = 0;
    for (int i = 1; i <= x; i++)
        res += phi[i];
    return res;
}

int main()
{
    cin >> n;
    cout << get_euler(n) << endl;
    return 0;
}

Ⅳ 快速幂

⒈快速幂

引

让我们先来思考一个问题：7^{10} 怎样算比较快？

方法1：最朴素的想法是 7\times7=49, 49\times7=343, \cdots，一步一步算，共进行了 9 次乘法。这样算无疑太慢了，尤其对计算机而言，每次运算只乘上一个个位数，无疑太屈才了。这时我们想到，也许可以拆分问题。

方法2：先算 7^5，再算它的平方，共进行了 5 次乘法。但这并不是最优解，因为对于 7^5，我们仍然可以拆分问题。

方法3：先算 7\times7=49，则 7^5=49\times49\times7，再算它的平方，共进行了 4 次乘法。

模仿这样的过程，我们得到一个在 \Theta(\log n) 时间内计算出幂的算法，也就是快速幂。

递归快速幂

递归方程：

Code

//递归快速幂
int qpow(int a, int n)
{
    if (n == 0)
        return 1;
    else if (n % 2 == 1)
        return qpow(a, n - 1) * a;
    else
    {
        int temp = qpow(a, n / 2);
        return temp * temp;
    }
}

//递归快速幂（对大素数取模）
#define MOD 1000000007
typedef long long ll;
ll qpow(ll a, ll n)
{
    if (n == 0)
        return 1;
    else if (n % 2 == 1)
        return qpow(a, n - 1) * a % MOD;
    else
    {
        ll temp = qpow(a, n / 2) % MOD;
        return temp * temp % MOD;
    }
}

注 大家知道，递归虽然简洁，但会产生额外的空间开销。我们可以把递归改写为循环，来避免对栈空间的大量占用，也就是非递归快速幂。

非递归快速幂

Code

//非递归快速幂
int qpow(int a, int n){
    int ans = 1;
    while(n){
        if(n&1)        //如果n的当前末位为1
            ans *= a;  //ans乘上当前的a
        a *= a;        //a自乘
        n >>= 1;       //n往右移一位
    }
    return ans;
}

快速幂模板题

[acwing] 875 - 快速幂

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

inline int read()
{
    register int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

inline long long qmi(int a, int k, int p)
{
    long long res = 1;
    while (k)
    {
        if (k & 1)
            res = (long long) res * a % p;
        k >>= 1;
        a = (long long) a * a % p;
    }
    return res;
}

int main()
{
    register int n = read();
    while (n--)
    {
        register int a, k, p;
        a = read(), k = read(), p = read();
        printf("%d\n", qmi(a, k, p));
    }
    return 0;
}

⒉ 快速幂求乘法逆元

定义

若整数 b,m 互质，并且 b\mid a，则存在一个整数 x，使得 \frac{a}{b}\equiv a\cdot x\ \pmod{m}，则称 x 为 b 的模 m 乘法逆元，记为 b^{-1}\ \pmod{m}。

模板

[acwing] 876 - 快速幂求逆元

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

int qmi(int a, int k, int p)
{
    int res = 1 % p;
    while (k)
    {
        if (k & 1)
            res = (long long)res * a % p;
        a = (long long)a * a % p;
        k >>= 1;
    }
    return res;

}

int main()
{
    int n;
    scanf("%d", &n);
    for (register int i(1); i <= n; ++i)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if (a % b == 0)
            printf("impossible\n");
        else
            printf("%d\n", qmi(a, b - 2, b));
    }
    return 0;
}

⒊ 扩展欧几里得算法(exgcd)

⑴ 裴蜀定理

裴蜀定理，又称贝祖定理（Bézout's lemma）。是一个关于最大公约数的定理。

其内容是：设 a,b 是不全为零的整数，则存在整数 x,y, 使得 ax+by=\text{gcd}\left(a,b\right).

证明

若任何一个等于 0, 则 \text{gcd}\left(a,b\right)=a. 这时定理显然成立。

若 a,b 不等于 0.

由于 \text{gcd}\left(a,b\right)=\text{gcd}\left(a,-b\right),

不妨设 a,b 都大于 0，a\geq b,\text{gcd}\left(a,b\right)=d.

对 ax+by=d, 两边同时除以 d, 可得 a_1x+b_1y=1, 其中 \left(a_1,b_1\right)=1.

转证 a_1x+b_1y=1.

我们先回顾一下辗转相除法是怎么做的，由 \text{gcd}\left(a,b\right)\to\text{gcd}\left(b,a\text{ mod }b\right)\to\cdots 我们把模出来的数据叫做 r 于是，有

把辗转相除法中的运算展开，做成带余数的除法，得

不妨令辗转相除法在除到互质的时候退出则 r_n=1 所以有（q 被换成了 x，为了符合最终形式）

即

由倒数第三个式子 r_{n-1}=r_{n-3}-x_{n-1}r_{n-2} 代入上式，得

然后用同样的办法用它上面的等式逐个地消去 r_{n-2},\cdots,r_1,

可证得 a_1x+b_1y=1. 这样等于是一般式中 d=1 的情况。

⑵ 扩展欧几里得算法

扩展欧几里得算法是欧几里得算法（又叫辗转相除法）的扩展。已知整数 a,b，扩展欧几里得算法可以在求得 a,b 的最大公约数的同时，能找到整数 x,y（其中一个很可能是负数），使它们满足裴蜀定理。

模板

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;
}

模板题

[acwing] 876 - 扩展欧几里得算法

Code

#include <bits/stdc++.h>
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;
}

int main()
{
    int n;
    scanf("%d", &n);
    while (n--)
    {
        int a, b, x, y;
        scanf("%d%d", &a, &b);
        exgcd(a, b, x, y);
        printf("%d %d\n", x, y);
    }
}

⑶ 线性同余方程

解形如 ax≡b(\text{mod }m) 的方程。

根据上面同余的理论可以得到 ax-b≡0(\text{mod }m)。

所以 m|ax-b，设 ax-b=-mk，可以得到一个不定方程 ax+mk=b。

解这个不定方程即可。

我们从这可以得出如果 \gcd(a,m)∤b 方程无解

Code - 模板

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

inline 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;
}

int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        int a, b, m;
        cin >> a >> b >> m;
        int x, y;
        int d = exgcd(a, m, x, y);
        if (b % d)
            puts("impossible");
        else
            printf("%d\n", (long long) b / d * x % m);
    }
    return 0;
}

⒋ 中国剩余定理

⑴ 算法简介及过程(来自OI Wiki)

中国剩余定理 (Chinese Remainder Theorem, CRT) 可求解如下形式的一元线性同余方程组（其中 n_1,n_2,\cdots,n_k 两两互质）：

⑵ C 语言代码(来自OI Wiki)

// C++ Version
LL CRT(int k, LL* a, LL* r) {
  LL n = 1, ans = 0;
  for (int i = 1; i <= k; i++) n = n * r[i];
  for (int i = 1; i <= k; i++) {
    LL m = n / r[i], b, y;
    exgcd(m, r[i], b, y);  // b * m mod r[i] = 1
    ans = (ans + a[i] * m * b % mod) % mod;
  }
  return (ans % mod + mod) % mod;
}

⑶ 典型习题

表达整数的奇怪方式

思路

代码(最近不知跟哪位大佬学的，离奇的码风↓)

#include<bits/stdc++.h>
#define _abs(x) (x^(x>>31))-(x >> 31)
#define qwq long long exgcd(long long a, long long b, long long &x, long long &y){if (!b){x = 1, y = 0;return a;}long long d = exgcd(b, a % b, y, x);y -= a / b * x;return d;}
using namespace std;
qwq
int main()
{
    int n;
    cin >> n;
    long long x = 0, a1, m1;
    cin >> a1 >> m1;
    for (register int i(0); i < n - 1; ++i)
    {
        long long a2, m2;
        cin >> a2 >> m2;
        long long k1, k2, d = exgcd(a1, -a2, k1, k2);
        if ((m2 - m1) % d)
        {
            x = -1;
            break;
        }
        k1 *= (m2 - m1) / d;
        k1 = (k1 % (a2 / d) + a2 / d) % (a2 / d);
        x = k1 * a1 + m1;
        long long a = _abs(a1 / d * a2);
        m1 = k1 * a1 + m1;
        a1 = a;
    }
    if (x != -1) x = (x % a1 + a1) % a1;
    cout << x << endl;
    return 0;
}