数论！！！

请先阅读[前言]后再阅读本博客

前言

============================================================

这一块是补充[前言]的

实现筛法的代码

• 埃拉托斯特尼筛法(Eratosthenes) 筛法

vector<int> prime;
bool is_prime[N];

void Eratosthenes(int n) {
  is_prime[0] = is_prime[1] = false;
  for (int i = 2; i <= n; ++i) is_prime[i] = true;
  for (int i = 2; i <= n; ++i) {
    if (is_prime[i]) {
      prime.push_back(i);
      if ((long long)i * i > n) continue;
      for (int j = i * i; j <= n; j += i)
        // 因为从 2 到 i - 1 的倍数我们之前筛过了，这里直接从 i
        // 的倍数开始，提高了运行速度
        is_prime[j] = false;  // 是 i 的倍数的均不是素数
    }
  }
}

• 筛至平方根

vector<int> prime;
bool is_prime[N];

void Eratosthenes(int n) {
  is_prime[0] = is_prime[1] = false;
  for (int i = 2; i <= n; ++i) is_prime[i] = true;
  // i * i <= n 说明 i <= sqrt(n)
  for (int i = 2; i * i <= n; ++i) {
    if (is_prime[i])
      for (int j = i * i; j <= n; j += i) is_prime[j] = false;
  }
  for (int i = 2; i <= n; ++i)
    if (is_prime[i]) prime.push_back(i);
}

• 分块筛选

int count_primes(int n) {
  constexpr static int S = 10000;
  vector<int> primes;
  int nsqrt = sqrt(n);
  vector<char> is_prime(nsqrt + 1, true);
  for (int i = 2; i <= nsqrt; i++) {
    if (is_prime[i]) {
      primes.push_back(i);
      for (int j = i * i; j <= nsqrt; j += i) is_prime[j] = false;
    }
  }
  int result = 0;
  vector<char> block(S);
  for (int k = 0; k * S <= n; k++) {
    fill(block.begin(), block.end(), true);
    int start = k * S;
    for (int p : primes) {
      int start_idx = (start + p - 1) / p;
      int j = max(start_idx, p) * p - start;
      for (; j < S; j += p) block[j] = false;
    }
    if (k == 0) block[0] = block[1] = false;
    for (int i = 0; i < S && start + i <= n; i++) {
      if (block[i]) result++;
    }
  }
  return result;
}

• 线性筛法

vector<int> pri;
bool not_prime[N];

void pre(int n) {
  for (int i = 2; i <= n; ++i) {
    if (!not_prime[i]) {
      pri.push_back(i);
    }
    for (int pri_j : pri) {
      if (i * pri_j > n) break;
      not_prime[i * pri_j] = true;
      if (i % pri_j == 0) {
        // i % pri_j == 0
        // 换言之，i 之前被 pri_j 筛过了
        // 由于 pri 里面质数是从小到大的，所以 i 乘上其他的质数的结果一定会被
        // pri_j 的倍数筛掉，就不需要在这里先筛一次，所以这里直接 break
        // 掉就好了
        break;
      }
    }
  }
}

============================================================

以下的看不看得懂无所谓，看就对了

证明 $\gcd(a,b)=\gcd(b,a\bmod b)$:

设$a=bk+c$x显然有 $c=a \bmod b$。设$d \mid a,~d \mid b$，则$c=a-bk, \frac{c}{d}=\frac{a}{d}-\frac{b}{d}k$。

由右边的式子可知 $\frac{c}{d} 为整数$，即 $d \mid c$，所以对于 $a,b$ 的公约数，它也会是 $b$,$a \bmod b$的公约数。

反过来也需要证明：

设 $d \mid b,~d\mid (a \bmod b)$，我们还是可以像之前一样得到以下式子 $\frac{a\bmod b}{d}=\frac{a}{d}-\frac{b}{d}k,~\frac{a\bmod b}{d}+\frac{b}{d}k=\frac{a}{d}$。

因为左边式子显然为整数，所以 $\frac{a}{d}$也为整数，即 $d \mid a$，所以 $b,a\bmod b$的公约数也是 $a,b$的公约数。

既然两式公约数都是相同的，那么最大公约数也会相同。

所以得到式子$\gcd(a,b)=\gcd(b,a\bmod b)$

实现：

// way：1
int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}

// way：2
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

裴蜀定理

定义

裴蜀定理，又称贝祖定理（Bézout's lemma）、贝祖等式（Bézout's identity）。是一个关于最大公约数的定理。

内容：

设$a,b$是不全为零的整数，对任意整数 $x,y$，满足$\gcd(a,b)\mid ax+by$，且存在整数$x,y$,使得$ax+by=\gcd(a,b)$.

证明

对于第一点

• 由于 $\gcd(a,b)\mid a,\gcd(a,b)\mid b$
• 所以 $\gcd(a,b)\mid ax,\gcd(a,b)\mid by$
• 其中$x,y$均为整数
• 因此$\gcd(a,b)\mid ax+by$

对于第二点

1.若任何一个等于$0$,则$\gcd(a,b)=a$,这时定理显然成立。

2.若$a,b$不等于 $0$

• 由于 $\gcd(a,b)=\gcd(a,-b)$
• 不妨设$a,b$都大于$0$，$a\geq b,\gcd(a,b)=d$
• 对$ax+by=d$,两边同时除以$d$,可得$a_1x+b_1y=1$,其中 $(a_1,b_1)=1$
• 转证$a_1x+b_1y=1$.

我们先回顾一下辗转相除法是怎么做的，由$\gcd(a, b) \rightarrow \gcd(b,a\mod b) \rightarrow \dots $我们把模出来的数据叫$r$于是，有

$$\gcd(a_1,b_1)=\gcd(b_1,r_1)=\gcd(r_1,r_2)=\cdots=(r_{n-1},r_n)=1 $$

把辗转相除法中的运算展开，做成带余数的除法，得

$$\begin{aligned}a_1 &= q_1b_1+r_1 &(0\leq r_1<b_1) \\ b_1 &= q_2r_1+r_2 &(0\leq r_2<r_1) \\ r_1 &= q_3r_2+r_3 &(0\leq r_3<r_2) \\ &\cdots \\ r_{n-3} &= q_{n-1}r_{n-2}+r_{n-1} \\ r_{n-2} &= q_nr_{n-1}+r_n \\ r_{n-1} &= q_{n+1}r_n\end{aligned} $$

不妨令辗转相除法在除到互质的时候退出则 $r_n=1$所以有（$q$被换成了 $x$，为了符合最终形式）

$$r_{n-2}=x_nr_{n-1}+1$$

即

$$1=r_{n-2}-x_nr_{n-1}$$

由倒数第三个式子 $r_{n-1}=r_{n-3}-x_{n-1}r_{n-2}$代入上式，得

$$1=(1+x_nx_{n-1})r_{n-2}-x_nr_{n-3}$$

然后用同样的办法用它上面的等式逐个地消去 $r_{n-2},\cdots,r_1$, 可证得$1=a_1x+b_1y$. 这样等于是一般式中 $d=1$的情况。

未完待续