简单数论学习笔记

注意标题:简单


素数

素性测试

  • Fermat 小定理乱搞
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),表示的是小于等于 nn 互质的数的个数。

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

一些性质

  • 欧拉函数是积性函数。

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

n 是奇数时,φ(2n)=φ(n)

  • n=p^k,其中 p 是质数,那么 φ(n)=p^k-p^{k-1}

求欧拉函数值

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}

  • 求出 1,2,···,n 中每个数关于 p的逆元。
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;
}

Zhang, Xuheng

这个人很懒,什么都没写

相关推荐

1 条评论

  1. qp

Leave a Reply

微信扫一扫

微信扫一扫

微信扫一扫,分享到朋友圈

简单数论学习笔记
返回顶部

显示

忘记密码?

显示

显示

获取验证码

Close