算法基础课-数论笔记

作者： 作者的头像   江寒辞 ,  2021-09-20 11:36:06 ,  所有人可见 ,  阅读 296

0


1

数论

1. 质数

1. 试除法判定质数

  • 朴素解法：O(n)

从2枚举到n - 1，看中间是否有数可以整除n，可以则是质数，否则就不是质数

  • 优化做法：O(sqrt(n))

  • 如果 n % d == 0，那么显而易见n % (n / d) == 0也是成立的。

  • 由于枚举的时候，是从小到大枚举，因此n <= (n / d)成立，那么可以得出d^2 <= n
  • 枚举的时候只需要枚举到sqrt(n)即可
bool check_prime_(int x) {
    if (x < 2)return false;
    for (int i = 2; i < x; i++) {
        if (x % i == 0)return false;
    }
    return true;
}

// 优化做法
bool check_prime(int x) {
    if (x < 2)return false;
    for (int i = 2; i <= x / i; i++) {
        if (x % i == 0)return false;
    }
    return true;
}

2. 分解质因数

  • 数学性质

  • 根据算数定理：任何一个数都可以写成x = p1^a1 + p2^a2 + ... + pn^an的形式，其中p打头的是质数

  • 任何一个数都只会有一个>= sqrt(x)的质因子，由反证法知，如果多于1一个这样的质因子，那他们的乘积将大于x。

  • 算法

  • 朴素解法：O(n)

    枚举2~n,计算质因子及其指数

    （注意：这种枚举方式中，会把合数筛除，比如16是2的倍数，也是4的倍数，但是由于是从小到大枚举，因此枚举到4的时候，数中已经不包含2的所有倍数了，因此不会吧4计算到质因子中，对于其他质因子同理）

  • 优化解法：O(sqrt(n))

    到sqrt(x)，当最后x>1成立，则说明x就是那个>sqrt(n)的质因子

void prime_factors(int x) {
    for (int i = 2; i <= x / i; i++) {
        if (x % i == 0) {
            int cnt = 0;
            while (x % i == 0) {
                x /= i;
                cnt++;
            }
            printf("%d %d\n", i, cnt);
        }
    }
    if (x > 1)printf("%d %d\n", x, 1);
}

3. 筛质数

  • 埃氏筛法：O(nlog(log(n)))
  • 从2枚举到n，枚举到未被标记的数，记录为质数，并且标记所有该数的倍数
void get_primes_normal(int x) {
    bool st[x + 1];
    int factors[x + 1], cnt = 0;
    memset(st, false, sizeof st);
    for (int i = 2; i <= x; i++) {
        if (st[i])continue;
        factors[cnt++] = i;
        for (int j = i + i; j <= x; j += i)
            st[j] = true;
    }
    printf("%d\n", cnt);
}
  • 线性筛法：O(n)
  • 每个0~x之间的合数，都只会被其最小的质因子筛掉
  • 核心代码中，由于质数是从小到大枚举的
    1. 当i % primse[j] == 0成立的时候，primes[j]一定是i的最小质因子,primes[j]也一定是primes[j]*i的最小质因子
    2. 当上面的条件不成立的时候，primes[j]一定比i中的所有质因子小
void get_primes_linear(int x) {
    // 初始化
    bool st[x + 1];
    int primes[x + 1], cnt = 0;
    memset(st, false, sizeof st);
    for (int i = 2; i <= x; i++) {
        // 未被标记的数，是质数
        if (!st[i])primes[cnt++] = i;
        // 从较小的质数开始枚举
        for (int j = 0; primes[j] <= x / i; j++) {
            st[i * primes[j]] = true;
            // 下面情况成立的时候，primes[j]一定是i的最小质因子,primes[j]也一定是primes[j]*i的最小质因子
            // 当上面的条件不成立的时候，`primes[j]`一定比`i`中的所有质因子小
            if (i % primes[j] == 0)break;
        }
    }
    printf("%d\n", cnt);
}

2. 约数

1. 试除法求约数

  • 算法思路：
  • 从1~sqrt(n)，依次枚举，计算约数
  • 当n % i == 0的时候，说明n / i也是你n的约数
void get_divisor(int x) {
    vector<int> divisors;
    for (int i = 1; i <= x / i; i++) {
        if (x % i == 0) {
            divisors.emplace_back(i);
            if (i != x / i)divisors.emplace_back(x / i);
        }
    }
    sort(divisors.begin(), divisors.end());
    for (const auto &item : divisors)printf("%d ", item);
    cout << endl;
}

2. 约数个数

  • 数学定理：
  • 根据算数定理：任何一个数都可以写成x = p1^a1 + p2^a2 + ... + pn^an的形式，其中p打头的是质数
  • 那么他的约数可以表示为 d=p1^b1 + p2^b2 + ... + pn^bn，其中0 <= bi <= ai
  • 根据排列组合定理，这个数的所有约数就是对应质因子指数的排列组合总数，即(a1+1)*(a2+1)* ... *(an+1)
const int MOD = 1e9 + 7;
unordered_map<int, int> primes;

// 求数组中所有数的乘积的约数个数
void divisors_cnt(vector<int> &nums) {
    for (auto num : nums) {
        for (int i = 2; i <= num / i; i++) {
            if (num % i != 0)continue;
            while (num % i == 0) {
                num /= i;
                primes[i]++;
            }
        }
        if (num > 1)primes[num]++;
    }
    long long res = 1;
    for (const auto &item : primes) {
        res = res * (item.second + 1) % MOD;
    }
    cout << res << endl;
}

3. 约数之和

  • 数学定理
  • 同上
  • 约数之和可以表示为 d=p1^b1 + p2^b2 + ... + pn^bn，其中0 <= bi <= ai的和
  • 把上面的式子合并过后就是(p1^0+p1^2+...+p1^a1)*(p2^0+p2^2+...+p2^a2)*...*(pn^0+pn^2+...+pn^an)
const int MOD = 1e9 + 7;
unordered_map<int, int> primes;

void divisors_sum(vector<int> &nums) {
    for (auto num : nums) {
        for (int i = 2; i <= num / i; i++) {
            if (num % i != 0)continue;
            while (num % i == 0) {
                num /= i;
                primes[i]++;
            }
        }
        if (num > 1)primes[num]++;
    }
    long long res = 1;
    for (const auto &item : primes) {
        long long t = 1;
        int p = item.first, cnt = item.second;
        for (int i = 1; i <= cnt; i++) {
            t = (p * t + 1) % MOD;
        }
        res = res * t % MOD;
    }
    cout << res << endl;
}

4. 最大公约数

  • 数学定理：
  • 如果x % d == 0 y % d == 0, 那么(a*x + b*y) % d == 0 也是成立的
  • 假设 x y两个数，则x % y == x - [x / y] * y，[]表示的取整，由于x y 已知，那么[x / y]可以看做常数c，即x % y == x - c * y
  • 由第一条可知，x % d == 0 y % d == 0时(x % y) % d == 0也成立
  • 算法：辗转相除法
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

3. 欧拉函数

1. 欧拉函数

  • 定义：设一个数N的欧拉函数记为phi[N]，其表达的含义是数N以内所有和N互质的数的个数（不包含N）
  • 公式：设p1 p2 p3 .. px表示的N所有的质因子，那么phi[N] = N * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/px)
  • 证明：容斥定理
int euler(int x) {
    int res = x;
    for (int i = 2; i <= x / i; i++) {
        if (x % i == 0) {
            while (x % i == 0) {
                x /= i;
            }
            res = res - res / i;
        }
    }
    if (x > 1)res = res - res / x;
    return res;
}

2. 筛法求欧拉函数

  • 题目：求某一个数范围内所有数的欧拉函数
  • 解题：基于动态规划思想和线性筛质数法求取答案
const int range = 1000010;
int phi[range];
bool st[range];

long long euler_sum(int x) {
    vector<int> primes;
    phi[1] = 1;
    memset(st, false, sizeof st);
    for (int i = 2; i <= x; i++) {
        // 一个数 i 如果是质数，那么它的欧拉函数的值是 i - 1
        if (!st[i]) {
            phi[i] = i - 1;
            primes.emplace_back(i);
        }
        for (int j = 0; primes[j] <= x / i; j++) {
            st[i * primes[j]] = true;
            if (i % primes[j] == 0) {
                phi[i * primes[j]] = phi[i] * primes[j];
                break;
            }
            phi[i * primes[j]] = phi[i] * (primes[j] - 1);
        }
    }
    long long res = 0;
    for (int i = 1; i <= x; i++)res += phi[i];
    return res;
}

3. 欧拉定理

  • 整数 [公式] 和 [公式] 除以 [公式] 的余数相同，则称 [公式] 模 [公式] 同余，计作

[公式]

  • 定理 ：设img，且img，则我们有:img

4. 快速幂

1. 快速幂

  • 场景：求a的k次方模上p的值

  • 算法思路：一个数可以用二进制表示，因此只需要列出二进制表示中bit位为1的幂方结果即可。相邻的的数bit对应的幂方数值相差一个平方，求取很简单。

typedef long long ll;

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

2. 快速幂求逆元

if (a % p == 0)printf("impossible\n");
else printf("%lld\n", qmi(a, p - 2, p));

5. 扩展欧几里得函数

1. 扩展欧几里得算法

详解

int ex_gcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int x1, y1;
    int gcd = ex_gcd(b, a % b, x1, y1);
    x = y1, y = x1 - a / b * y1;
    return gcd;
}

2. 线性同余方程

详解

int gcd = ex_gcd(a, a, x, y);
if (b % gcd != 0)printf("impossible\n");
else printf("%d\n", (long long) x * b / gcd % a);

6. 中国剩余定理

1. 线性同余方程组

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll ex_gcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    ll x1, y1;
    ll d = ex_gcd(b, a % b, x1, y1);
    x = y1, y = x1 - a / b * y1;
    return d;
}

int main() {
    int n;
    cin >> n;
    // x是方程的解 a1 m1是参数
    ll x, a1, m1;
    cin >> a1 >> m1;
    while (--n != 0) {
        ll a2, m2;
        cin >> a2 >> m2;
        ll k1, k2;
        ll d = ex_gcd(a1, a2, k1, k2);
        if ((m2 - m1) % d != 0) {
            cout << -1 << endl;
            return 0;
        }
        k1 = k1 * (m2 - m1) / d;
        // 把k1变成一个尽可能小的正数
        ll mod = abs(a2 / d);
        k1 = (k1 % mod + mod) % mod;
        m1 = m1 + k1 * a1;
        a1 = abs(a1 * a2 / d);
    }
    cout << m1 << endl;
    x = (m1 % a1 + a1) % a1;
    cout << x << endl;
    return 0;
}

0 评论

1024
x