简单数论学习笔记

Hello, 欢迎登录 or 注册!

/ 1评 / 0

本文作者:  本文分类:编程学习笔记  浏览:1240
阅读时间:2970字, 约3.5-5分钟

注意标题:简单


素数

素性测试

bool millerRabin(int n) {
  if (n < 3) return n == 2;
  // test_time 为测试次数,建议设为不小于 8
  // 的整数以保证正确率,但也不宜过大,否则会影响效率
  for (int i = 1; i <= test_time; ++i) {
    int a = rand() % (n - 2) + 2;
    if (quickPow(a, n - 1, n) != 1) return 0;
  }
  return 1;
}

显然有出错概率。

比较正确的:

bool millerRabbin(int n) {
  if (n < 3) return n == 2;
  int a = n - 1, b = 0;
  while (a % 2 == 0) a /= 2, ++b;
  // test_time 为测试次数,建议设为不小于 8
  // 的整数以保证正确率,但也不宜过大,否则会影响效率
  for (int i = 1, j; i <= test_time; ++i) {
    int x = rand() % (n - 2) + 2, v = quickPow(x, a, n);
    if (v == 1 || v == n - 1) continue;
    for (j = 0; j < b; ++j) {
      v = (long long)v * v % n;
      if (v == n - 1) break;
    }
    if (j >= b) return 0;
  }
  return 1;
}

求因子数一定的最小数。

#include <bits/stdc++.h>
using namespace std;
#define ULL unsigned long long
#define INF ~0ULL
ULL p[16] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};
ULL ans;
ULL n;
// depth: 当前在枚举第几个素数。num: 当前因子数。
// temp: 当前因子数量为 num
// 的时候的数值。up:上一个素数的幂,这次应该小于等于这个幂次嘛
void dfs(ULL depth, ULL temp, ULL num, ULL up) {
    if (num > n || depth >= 16) return;
    if (num == n && ans > temp) {
        ans = temp;
        return;
    }
    for (int i = 1; i <= up; i++) {
        if (temp / p[depth] > ans) break;
        dfs(depth + 1, temp = temp * p[depth], num * (i + 1), i);
    }
}

int main() {
    while(scanf("%llu", &n) != EOF) {
        ans = INF;
        dfs(0, 1, 1, 64);
        printf("%llu\n", ans);
    }
    return 0;
}

最大公约数

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

以上为欧几里得求法。时间复杂度为 $O(log$ $n)$。

多个数的最大公约数

扩展欧几里得定理

常用于求 $ax+by=gcd(a,b)$ 的一组可行解。

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

欧拉函数

定义

即 $φ(n)$,表示的是小于等于 $n$ 和 $n$ 互质的数的个数。

当 $n$ 是质数的时候,显然有 $φ(n)=n-1$。

一些性质

如果有 $gcd(a,b)=1$,那么 $φ(a×b)=φ(a)×φ(b)$

当 $n$ 是奇数时,$φ(2n)=φ(n)$。

求欧拉函数值

int euler_phi(int n) {
    int ans = n;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) {
            ans = ans / i * (i - 1);
            while (n % i == 0) n /= i;
        }
    if (n > 1) ans = ans / n * (n - 1);
    return ans;
}

欧拉定理

若 $gcd(a,m)=1$,则 $a^{φ(m)}≡1(mod$ $m)$。

扩展欧拉定理


素数筛法

埃氏筛法

int Eratosthenes(int n) {
    int p = 0;
    for (int i = 0; i <= n; ++i) is_prime[i] = 1;
    is_prime[0] = is_prime[1] = 0;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            prime[p++] = i;  // prime[p]是i,后置自增运算代表当前素数数量
            if ((long long)i * i <= n)
                for (int j = i * i; j <= n; j += i)
                    // 因为从 2 到 i - 1 的倍数我们之前筛过了,这里直接从 i
                    // 的倍数开始,提高了运行速度
                    is_prime[j] = 0;  // 是i的倍数的均不是素数
        }
    }
    return p;
}

时间复杂度为 $O(log$ $log$ $n)$。

欧拉筛法

void init() {
  phi[1] = 1;
  for (int i = 2; i < MAXN; ++i) {
    if (!vis[i]) {
      phi[i] = i - 1;
      pri[cnt++] = i;
    }
    for (int j = 0; j < cnt; ++j) {
      if (1ll * i * pri[j] >= MAXN) break;
      vis[i * pri[j]] = 1;
      if (i % pri[j]) {
        phi[i * pri[j]] = phi[i] * (pri[j] - 1);
      } else {
        // i % pri[j] == 0
        // 换言之,i 之前被 pri[j] 筛过了
        // 由于 pri 里面质数是从小到大的,所以 i 乘上其他的质数的结果一定也是
        // pri[j] 的倍数 它们都被筛过了,就不需要再筛了,所以这里直接 break
        // 掉就好了
        phi[i * pri[j]] = phi[i] * pri[j];
        break;
      }
    }
  }
}

时间复杂度为 $O(n)$。


裴蜀定理

设 $a,b$ 是不全为零的整数,则存在整数 $x,y$, 使得 $ax+by=gcd(a,b)$。


乘法逆元

如果一个线性同余方程 $ax≡1(mod$ $b)$,则 $x$ 称为 $a$ $mod$ $b$ 的逆元,记作 $a^{-1}$。

inv[1] = 1;
for (int i = 2; i <= n; ++i) {
  inv[i] = (long long)(p - p / i) * inv[p % i] % p;
}

线性同余方程

形如 $ax≡c(mod$ $b)$ 的方程被称为线性同余方程。

方程 $ax+by=c$ 与方程 $ax≡c(mod$ $b)$ 是等价的。整数解的充要条件为 $gcd(a,b)|c$。

int ex_gcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int d = ex_gcd(b, a % b, x, y);
    int temp = x;
    x = y;
    y = temp - a / b * y;
    return d;
}
bool liEu(int a, int b, int c, int& x, int& y) {
    int d = ex_gcd(a, b, x, y);
    if (c % d != 0) return 0;
    int k = c / d;
    x *= k;
    y *= k;
    return 1;
}

关于作者

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注