前言

开个大坑。

正文

质数

• 质数的个数是无限的。
• 试除法：若一个正整数 \(N\) 为合数，则存在一个能整除 \(N\) 的数 \(T\) ，其中 \(2 \le T \le \sqrt{N}\) 。
  • 时间复杂度为 \(O(\sqrt{n})\) 。
  • 代码实现

  bool isprime(int n)
  {
      if (n < 2)
          return false;
      for (int i = 2; i <= sqrt(n); i++)
          if (n % i == 0)
              return false;
      return true;
  }
  

• 筛法
  • Eratosthenes 筛法（埃式筛法）
    • 时间复杂度 \(O(n \times \log \log n)\)
    • 例题
      • luogu P3912 素数个数

      #include <bits/stdc++.h>
      using namespace std;
      bool m[100000010];
      int main()
      {
          int n, i, j, ans = 0;
          cin >> n;
          m[1] = 1;
          for (i = 2; i <= sqrt(n); i++)
          {
              if (m[i] == 0)
              {
                  for (j = 2; i * j <= n; j++)
                  {
                      m[i * j] = 1;
                  }
              }
          }
          for (i = 2; i <= n; i++)
          {
              if (m[i] == 0)
              {
                  ans++;
              }
          }
          cout << ans;
          return 0;
      }
      

  • 线性筛法（欧拉筛法）
    • 时间复杂度 \(O(n)\)
    • 例题
      • luogu P3383 【模板】线性筛素数

      #include <bits/stdc++.h>
      using namespace std;
      #define ll long long
      #define sort stable_sort
      #define endl '\n'
      int prime[100000001], sum[10], len = 0;
      bool vis[100000001];
      void isprime(int n)
      {
          int i, j;
          memset(vis, false, sizeof(vis));
          for (i = 2; i <= n; i++)
          {
              if (vis[i] == false)
              {
                  len++;
                  prime[len] = i;
              }
              for (j = 1; j <= len && i * prime[j] <= n; j++)
              {
                  vis[i * prime[j]] = true;
                  if (i % prime[j] == 0)
                  {
                      break;
                  }
              }
          }
      }
      int main()
      {
          int n, q, i, k;
          cin >> n >> q;
          isprime(n);
          for (i = 1; i <= q; i++)
          {
              cin >> k;
              cout << prime[k] << endl;
          }
          return 0;
      }
      

• 算术基本定理（唯一分解定理）
  • 任何一个大于 \(1\) 的正整数都能唯一分解成有限个的质数的乘积，可写作 \(N=p_1^{c_1}p_2^{c_2}……p_m^{c_m}\) ，其中 \(c_i\) 都是正整数， \(p_i\) 都是质数，且满足 \(p_1<p_2<……<p_m\) 。

同余

• 自反性： \(a \equiv a \pmod{p}\)
• 对称性：若 \(a \equiv b \pmod{p}\) ，则 \(b \equiv a \pmod{p}\) 。
• 传递性：若 \(a \equiv b \pmod{p},b \equiv c \pmod{p}\) ，则 \(a \equiv c \pmod{p}\) 。
• 同加性：若 \(a \equiv b \pmod{p}\) ，则 \(a+c \equiv b+c \pmod{p}\) 。
• 同乘性：若 \(a \equiv b \pmod{p}\) ，则 \(a \times c \equiv b \times c \pmod{p}\) 。
• 一般情况下不满足同除性。
  • 特例：当 \(\gcd(c,p)=1,a \times c\equiv b \times c \pmod{p}\) 时，则 \(a \equiv b \pmod{p}\) 。
• 同幂性：若 \(a \equiv b \pmod{p}\) ，则 \(a^n \equiv b^n\pmod{p}\) 。
• 若 \(p,q\) 互质，\(a \bmod p=x,a \bmod q=x\) ，则 \(a \bmod(p \times q)=x\) 。

最大公约数

• 取模运算性质
  • \((a+b) \bmod p=((a \bmod p)+(b \mod p)) \mod p\) ，反之亦成立。
  • \((a-b) \bmod p=((a \bmod p)-(b \mod p)) \mod p\) ，反之亦成立。
  • \((a \times b) \bmod p=((a \bmod p) \times (b \mod p)) \mod p\) ，反之亦成立。
  • 引流两篇讲解负数取模的文章 link1 link2
• 若 \(\forall a,b \in \mathbb{N}\) ，则 \(\gcd (a,b) \times \operatorname{lcm} (a,b)=a \times b\) 。
• 九章算术·更相减损术
  • 若 \(\forall a,b \in \mathbb{N},a \le b\) ，则 \(\gcd (a,b)= \gcd (a,b-a)= \gcd (b,b-a)\) 。
    • 证明：设 \(d= \gcd (a,b),k_1= \frac{a}{d},k_2= \frac{b}{d}\) ，移项得 \(a=k_1 d,b=k_2 d\) ，又因为 \((b-a) \bmod d=0,b-a=(k_2-k_1)d\) ，故 $\gcd (a,b-a)= \gcd (k_1 d,(k_2-k_1)d)=d $ ，\(b\) 与 \(b-a\) 同理。
  • 若 \(\forall a,b \in \mathbb{N}\) ，则 \(\gcd (2a,2b)= 2\gcd (a,b)\) 。
• 欧几里得算法
  • 若 \(\forall a,b \in \mathbb{N}\) ，则 \(\gcd (a,b)= \gcd(b,a \bmod b)\) 。
    • 证明
      • 若 $a<b $ ，则 \(\gcd(b,a \bmod b)=\gcd(b,a)=\gcd(a,b)\) 。
      • 若 \(a \ge b\) ，设 $ d= \gcd(a,b),a=q \times b+r(0 \le r <b)$ ，则 \(r=a \bmod b=a-q \times b\) ，又因为 $ d|a,d|b,d|(q \times b) $ ，则 \(d|(a-q \times b)\) ，即 \(d|r\) ，故 \(\gcd(a,b)=\gcd(b,r)=\gcd(b,a \bmod b)\) 。
  • 时间复杂度为 \(O(\log \max(a,b))\) 。
  • 代码实现

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