📖Mosquito's Note📖

数论

待总结

  • ( A + B ) % k = 0 <=> A % k = -B % k

  • A % k = a => A * 10 ^ n % k = a * 10 ^ n % k

  • 一个负数模一个数在 cpp 中为负数，但在数学中的余数必须是正数，例如：-5 % 3 = -2 但在数学中结果应该是 1，因此需要做转换 ( -5 % 3 + 3 ) % 3 = 1

  • 1 - n 中 p 的倍数的个数 为 [n / p]，[] 表示向下取整

素数判定

试除法

若某数 n 从 2 到 n\sqrt{n} 中都没有因数字，则这个数就是素数。试除法就是暴力地验证素数的方式。

复杂度：

  • 时间：O(n)O(\sqrt{n})
#include <iostream>

using namespace std;
const int N = 110;

int n;
bool checkPrime(int n)
{
    if (n == 1) return false;
    for (int i = 2 ; i <= n / i ; i ++)
            if (n % i == 0) return false;

    return true;
}

int main()
{
    cin >> n;
    while (n --)
    {
        int x;
        cin >> x;
        if (checkPrime(x)) puts("Yes");
        else puts("No");

    }

    return 0;
}

扩展---试除法求约数

和试除法判断素数的思路一样。

复杂度：

  • 时间：O(n)O(\sqrt{n})
#include <iostream>
#include <vector>

using namespace std;

int n;

vector<int> getDivide(int x)
{
    vector<int> d;

    for (int i = 1 ; i <= x / i ; i ++)
    {
        if (x % i == 0)
        {
            d.push_back(i);
            if (i != x / i) d.push_back(x / i); // 注意把另一个约数也加入集合。
        }
    }

    return d;
}

int main()
{
    cin >> n;

    while (n --)
    {
        int x;
        cin >> x;
        auto res = getDivide(x);

        for (auto i : res) cout << i << ' ';
        puts("");
    }

    return 0;
}

因素分离（分解质因数）

试除筛法

筛法只选出质数的原因：

可证明：若某数 n 含有因子 i 且 i 能被 2 到 i - 1 中的某些数整除（i 是合数），那么 n 也能被 2 到 i - 1 中的这些数整除，因此 i 被筛选出来前已经被除干净了，所以该方法只能筛出质因数。（其实也说明了任何一个合数都可分解为若干质数相乘）

复杂度：

  • 时间：O(n)O(\sqrt{n})
#include <iostream>

using namespace std;

int n;

void divide(int x)
{
    for (int i = 2 ; i <= x / i ; i ++) {
        int cnt = 0;
        while (x % i == 0) x /= i, cnt ++;
        cout << i << ' ' << cnt << endl;
    }
    if (x > 1) cout << x << ' ' << 1 << endl; //x 中最多有一个大于 sqrt(x)的质因数

    cout << endl;
}

int main()
{
    cin >> n;

    while (n -- )
    {
        int x;
        cin >> x;
        divide(x);
    }

    return 0;
}

扩展——约数的个数

由分解质因数部分可知，任何一个合数N都可以写成N=p1a1p2a2...pkakN = p_1^{a_1}p_2^{a_2}...p_k^{a_k}，即若干个质数的若干次幂的积，所以N的任意约数 d 都可以表示为d=p1b1p2b2...pkbk,0≤bk≤akd = p_1^{b_1}p_2^{b_2}...p_k^{b_k}, 0\leq b_k \leq a_k 那么，约数的个数就为(a1+1)∗...∗(ak+1)(a_1 + 1) * ... * (a_k + 1)，即组合数

#include <iostream>
#include <unordered_map>

using namespace std;
typedef long long ll;
const int Mod = 1e9 + 7;

unordered_map<int, int> primes;

int n;
ll res = 1;
int main()
{
    cin >> n;
    while (n --)
    {
        int x;
        cin >> x;

        for (int i = 2 ; i <= x / i ; i ++)
        {
            while (x % i == 0) primes[i] ++, x /= i;
        }
        if (x > 1) primes[x] ++;
    }

    for (auto p : primes) res = res * (p.second + 1) % Mod;

    cout << res << endl;
    return 0;
}

扩展——约数之和

由前面的分析知道了，一个合数的任何约数可以表示为d=p1b1p2b2...pkbk,0≤bk≤akd = p_1^{b_1}p_2^{b_2}...p_k^{b_k}, 0\leq b_k \leq a_k，所以一个合数的所有约数之和（即(a1+1)...(ak+1)(a_1 + 1)...(a_k + 1)个因数之和）可以写为：(p10+p11+...+p1a1)(p20+p22+...+p2a2)...(pk0+pk1+...+pkak)( p_1^0 + p_1^1 + ... +p_1^{a_1} )( p_2^0 + p_2^2 + ... +p_2^{a_2} )...( p_k^0 + p_k^1 + ... +p_k^{a_k} )，展开即得到所有质数选取任意次幂的全部组合之和。

#include <iostream>
#include <unordered_map>

using namespace std;
typedef long long ll;
const int Mod = 1e9 + 7;

unordered_map<int, int> primes;

int n;
ll res = 1;
int main()
{
    cin >> n;
    while (n --)
    {
        int x;
        cin >> x;

        for (int i = 2 ; i <= x / i ; i ++)
        {
            while (x % i == 0) primes[i] ++, x /= i;
        }
        if (x > 1) primes[x] ++;
    }

    for (auto prime : primes)
    {
        ll t = 1;
        int p = prime.first, a = prime.second;
        while (a --) t = (t * p + 1) % Mod;
        res = (res * t) % Mod;
    }

    cout << res << endl;
    return 0;
}

欧拉函数

1∼N 中与 N 互质的数的个数被称为欧拉函数，记为 Φ(N)\Phi(N) 。 在算数基本定理中，N=p1a1p2a2...pmamN = p_1^{a_1}p_2^{a_2}...p_m^{a_m}

Φ(N)=N∗p1−1p1∗p2−2p2∗...∗p2−mpm\Phi(N) = N * \frac{p_1 - 1}{p_1} * \frac{p_2 - 2}{p_2} * ... * \frac{p_2 - m}{p_m}

#include <bits/stdc++.h>

using namespace std;
int n;

int main() {
    cin >> n;

    while (n --)
    {
        int x;
        cin >> x;
        int res = x;

        for (int i = 2 ; i <= x / i ; i ++)
            if (x % i == 0)
            {
                res = res / i * (i - 1);
                while (x % i == 0) x /= i;
            }

        if (x > 1) res = res / x * (x - 1);
        cout << res << endl;
    }
    return 0;
}

素数筛选

朴素法

在2~n中，通过把一个数的倍数删除掉的方式来筛选质数，若遇到没被删除的数，则把它加入质数的集合中。

复杂度：

  • 时间：O(nlogn)O(nlogn)
#include <iostream>

using namespace std;
const int N = 1e6 + 10;
int primes[N], cnt;
bool st[N];

int n;
int main()
{
    cin >> n;

    for (int i = 2 ; i <= n ; i ++)
    {
        if (!st[i])
        {
            primes[cnt ++] = i;
        }

        for (int j = i ; j <= n ; j += i) st[j] = true;
    }

    cout << cnt << endl;

    return 0;
}

埃氏筛法

容易发现朴素筛法会把同样的合数重复删除多次，而埃氏筛法优化于朴素筛法，可以由分解质因数部分的证明知道，每一个合数都能分解为若干质数相乘，因此只需要使用选出的素数去删除合数。

复杂度：

  • 时间：O(nloglogn) 可近似于 n
#include <iostream>

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

int n;
int main()
{
    cin >> n;

    for (int i = 2 ; i <= n ; i ++)
    {
        if (!st[i])
        {
            primes[cnt ++] = i;
            for (int j = i ; j <= n ; j += i) st[j] = true;
        }
    }

    cout << cnt << endl;

    return 0;
}

线性筛法

埃氏筛法，已经快速很多了，但还是会发生重复删除同一个合数的情况。而线性筛法每次只使用某合数的最小质因子筛掉合数，这样就能避免重复筛选。

复杂度：

  • 时间：O(n)O(n)
#include <iostream>

using namespace std;
const int N = 1e6 + 10;
int primes[N], cnt;
bool st[N];

int n;
int main()
{
    cin >> 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;  //优化到 n 的关键
        }
    }
    cout << cnt << endl;

    return 0;
}

为什么i % p[j] == 0时break，可以证明：

当 i % p[j] == 0时，设m = i / p[j]，则i * p[j + 1] = ( m * p[j + 1] ) * p[j]

设k = m * p[j + 1]，则可得到i * p[j + 1] = k * p[j]，即i * p[j + 1]是p[j]的若干倍，这说明：如果不在i % p[j] == 0时break，那么i * p[j + 1]这个合数将会在i = k时又被筛一遍，此时退出可以避免重复筛选。

最大公约数/最小公倍数

欧几里得算法（辗转相除法）

数论的基础知识：若 d|a 且 d|b 则 d|ax+by （d|a 表示 d 能整除 a，x，y 为任意常数）

证明：

设 c = floor(a/b)，则 a % b = a - c * b

则设 a 与 b 的公约数为 d，由基础知识：d|a 且 d|b，则有 d|a - c * b

那么可以得到(a, b) = (b, a % b)，即左边两数任何公约数都是右边两数的公约数，最终可以得到 gcd(a, b) = gcd(b, a % b)，它们的最大公约数也相等

交换 a 和 b 的位置是为了保证 a 永远大于 b ，以便递归能一直进行下去，当递归运算到 gcd(a, 0)时，可以知道 ax + by = a，此时返回 a

#include <iostream>

using namespace std;

int n;

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

int main()
{
    cin >> n;

    while (n -- )
    {
        int a, b;
        cin >> a >> b;

        cout << gcd(a, b) << endl;
    }
    return 0;
}

最小公倍数公式：最小公倍数 d = ( A * B ) / gcd(A, B)

直觉上的证明（非常不严谨，只是方便记忆）:

A × B = a × c × b × c (c = gcd(A, B)，a = A / c，b = B / c)

因为 c 为 A, B 的最大公因数，因此 a 与 b 是互质的，而两质数的最小公倍数就是它们的乘积，那么 a × b | d

又因为 d|A × B，即 d|a × b × c × c

又由 A|d，B|d 可以知道 d = [a × b × c， a × b × c × c]

  1. 当 A 与 B 互质，c = gcd(A, B) = 1，d 取 a × b × c × c 满足 A × B = d × c
  2. 当 A 与 B 互质，c = gcd(A, B) > 1，d 取 a × b × c 满足 A × B = d × c
  3. 当 A|B or B|A ，c = A or B，则 a = 1, b = B / A or a = A / B, b = 1 ，d 取 a × b × c 满足 A × B = d × c

综上可得：d = (A × B) / gcd(A, B)

贴一个完美证明的博客： 点击跳转open in new window

#include <iostream>

using namespace std;

int n;

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

int main()
{
    cin >> n;

    while (n -- )
    {
        int a, b;
        cin >> a >> b;

        cout << a * b / gcd(a, b) << endl;
    }
    return 0;
}

扩展欧几里得算法

再次由数论的基础知识：若 d|a 且 d|b 则 d|ax+by （d|a 表示 d 能整除 a，x，y 为任意常数）

可以知道 存在 x， y，使得a * x + b * y = gcd(a, b)
又因为 gcd(a, b) = gcd(b, a % b)，则
b * x' + a % b * x' = gcd(b, a % b)
b * x' + ( a - [a / b] * b ) * x' = gcd(b, a % b) ， []表示向下取整
a * x' + b * (x' - [a / b] * x') = gcd(b, a % b) = gcd(a, b)

则可以得到 {x=y′y=x′−⌊a/b⌋∗y′\left\{\begin{matrix} x = y' \\ y = x' - \left\lfloor a/b \right\rfloor * y' \end{matrix}\right. ，因此可以通过递归的方式求解出 x, y

注意：这里的 x 和 y 是 gcd(a, b)对应的参数， 而 x', y' 是 gcd(b, a % b)对应的参数。

边界：当 b = 0 时，可以知道 ax * by = a，则 x = 1，y = 0

#include <iostream>

using namespace std;

int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    else
    {
        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, x, y;;
        cin >> a >> b;
        int t = exgcd(a, b, x, y);
        cout << x << ' ' << y << endl;
    }

    return 0;
}

线性同余方程

注意：exgcd(a, b, x, y) 与 ax+by=gcd(a,b)ax + by = gcd(a, b)中的 b 实际上是ax≡gcd(a,b)(mod b)ax \equiv gcd(a, b) (mod \space b)中的 b

#include <iostream>

using namespace std;

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

int main()
{
    cin >> n;

    while (n -- )
    {
        int a, b, m, x, y;
        cin >> a >> b >> m;
        int d = exgcd(a, m, x, y);

        if (b % d) puts("impossible");
        else cout << 1LL * x * b / d % m << endl;
    }

    return 0;
}

逆元

若存在 b，使得b∣a,a/b≡a∗x(mod p)b|a, a/b \equiv a * x (mod \space p)
两边同乘 b 可得到a≡a∗x∗b(mod p)a \equiv a * x * b (mod \space p)
两边同约 a 可得到b∗x≡1(mod p)b * x \equiv 1 (mod \space p)
则称 x 为 b 模 p 的乘法逆元，记为b−1(mod p)b^{-1}(mod \space p)

当且仅当 b 与 p 互质时，b 才有逆元

b 为 p 的倍数时，b * x % p = 0 ，x 为任意整数，那么 b 乘于逆元模 p 为 0 而不为 1，因此当 b 与 p 不互质时，b 没有模 p 的乘法逆元

逆元的作用：当模上一个数时，乘于数的逆元同等于除上这个数，那么可以避免做除法运算。

快速幂求逆元

费马小定理：当 p 为质数，a 为任意自然数且 a 与 p 互质时，有ap≡a(mod p)a^p \equiv a (mod \space p) 可化简为ap−2∗a≡1(mod p)a^{p-2} * a \equiv 1(mod \space p)
那么，当且仅当 p 为质数且 a 与 p 互质时，可以由费马小定理得到 a 模 p 的乘法逆元为ap−2a^{p-2}

#include <iostream>

using namespace std;
typedef long long LL;

LL qmi(int a, int k, int mod)
{
    LL res = 1;
    while (k)
    {
        if (k & 1) res = res * a % mod;
        a = 1LL * a * a % mod;
        k >>= 1;
    }
    return res;
}
int main()
{
    int n;
    cin >> n;

    while (n -- )
    {
        int a, p;
        cin >> a >> p;
        LL ans = qmi(a, p - 2, p);
        if (a % p == 0) puts("impossible");
        else cout << ans << endl;
    }

    return 0;
}

扩展欧几里得算法求逆元

费马小定理成立的前提是 p 为质数，如果 p 为合数，只能通过扩展欧几里得算法求逆元了
由之前的分析知道，当且仅当 a 与 p 互质时， a 才有逆元，即gcd(a,p)=1gcd(a, p) = 1

假设 a 的逆元为 x，则有a∗x≡1(mod p)a * x \equiv 1 (mod \space p)
即a∗x+p∗y=1a * x + p * y = 1 那么可以用 exgcd(a, p, x, y)，求解 x.

#include <iostream>

using namespace std;

int n;

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

int main()
{
    cin >> n;

    while (n -- )
    {
        int a, b, x, y;
        cin >> a >> b;

        int t = exgcd(a, b, x, y);
        if (t == 1) cout << (1LL * x % b + b) % b << endl;  //扩展欧几里得算法得到的数可能是负的，但是数学中 mod 的结果必须为正，因此转换成正数。
        else puts("impossible");
    }
    return 0;
}