2019-03-23

省选复习

11 分钟读完 (大约 1656 个字)

省选基础数论整理

众所周知，$\text{LiM}$数学不好。
这篇文章用于总结一堆数论算法。

$\text{Primality Test}$

单个$\mathcal{O(\sqrt{n}):}$
由于因数成对出现，找有没有$\leq \sqrt{n}$的因子即可判断。

bool isprime(int n) {
  for(int i = 2; i * i <= n; i++)
    if(n % i == 0) return 0;
  return 1;
}

$\mathcal{O(nlogn):}\text{Normal Sieve}$

void sieve() {
  notprime[1] = 1;
  for(int i = 2; i <= n; i++) {
    for(int j = i + i; j <= n; j++) notprime[j] = 1;
  }
}

复杂度由调和级数证明。
$\mathcal{O(nloglogn):}\text{Eratothene Sieve}$
只筛素数。
反正根据素数分布来看大概是$\mathcal{O(nloglogn)}$的，具体不会证（雾

void sieve() {
  notprime[1] = 1;
  for(int i = 2; i <= n; i++) {
    if(!notprime[i])
      for(int j = 2; i*j <= n; j++) notprime[i*j] = 1;
  }
}

$\mathcal{O(n):}\text{Euler Sieve}$
保证每个数都只能被最小的质因子筛到一次，所以复杂度是对的。
还可以用于筛一些积性函数。

void sieve() {
  for(int i = 2; i <= n; i++) {
    if(!!np[i]) prime[++tot] = i;
    for(int j = 1; j <= tot && i * prime[j] <= n; j++) {
      np[i * prime[j]] = 1;
      if(i % prime[j] == 0) break;
    }
  }
}

只筛一次的证明：
观察这一行：

1	if(i % prime[j] == 0) break;

考虑这样做代表着什么。显然， $i$ 可以表示成$k\times prime[j].$

如果不$break$，那么筛下一个 $prime$ 的时候：就有

$i\times prime[j+1] = k\times prime[j]\times prime[j+1]$

违背了只被最小质因子筛的规定。

$\mathcal{O(klogn):}\text{Miller Rabin}$

理论背景：费马小定理。
$设p \in prime，a$是整数，且$(a,p)=1$，就有$a^{p-1}\equiv 1\mod p$
证明：
还是举个例子吧。比如说$p=13,a=3$.
那么对于$[1,p-1]$之间的整数（也就是$1,2,3…p-1$），我们同乘一个$a$，变成$a,2a,…(p-1)a$。
我们发现乘完之后，整数中没有一个$\mod p=0$（$(a,p)=1$），也没有两个$\mod p$相等（基本性质）。所以模完之后一定是$[1…p-1]$的一个排列。也就是

$a\times 2a\times...\times (p-1)a\equiv (p-1)!\pmod p$

提出来$a$：$a^{p-1}\times(p-1)!\equiv (p-1)!\pmod p$
提出来$(p-1)!$：$a^{p-1}\equiv 1\pmod p)$.得证。

那么发现上面那个式子同乘$a$就是$a^p\equiv a\pmod p$。
这个式子在$p$是素数时一定有，但是有这个式子不代表$p$一定是素数。

因此引入二次探测。
首先证明一个东西：$x^2\equiv 1\pmod p$，且$x ≠ (p-1)\pmod p$，$x ≠ 1\mod p$，那么这个$p$一定是合数。

证明：
$x^2\equiv 1\pmod p$
$x^2 - 1\equiv 0\pmod p$
$(x+1)(x-1)\equiv 0\pmod p$

由于$p$是质数，那么如果他俩乘起来模$p$等于$0$，那么要么
$(x+1)\equiv 0\pmod p \rightarrow x=p-1\pmod p$
要么
$(x-1)\equiv 0\pmod p \rightarrow x=1\pmod p$
然后，我们发现，费马小定理里头给出的有关$p$的式子是$a^{p-1}\equiv 1\pmod p$。于是可以将$p-1$分解为$2^k\times t$，然后先计算出来$a^t\mod p$，再不断地将$t$翻倍。其中，如果有一次满足$a^{(2t)}\equiv 1\pmod p$且$a^t ≠ \pm 1\pmod p$，那就一定是合数。

不难发现每次翻倍最多翻log次，所以复杂度是对的。

/**
 * @Author: Mingyu Li
 * @Date:   2019-03-24T22:33:04+08:00
 * @Last modified by:   Mingyu Li
 * @Last modified time: 2019-03-29T21:02:44+08:00
 */
#include <bits/stdc++.h>
#define Go(i , x , y) for(register int i = x; i <= y; i++)
#define God(i , y , x) for(register int i = y; i >= x; i--)
#define ll long long
ll n , m;

ll primelist[8] = {2 , 3 , 7 , 13 , 41 , 59 , 97};
ll quickt(ll u , ll p , ll t) {
  if(!p) return 1%t;
  ll half = quickt(u , p/2 , t);
  if(p % 2) return half * half % t * u % t;
  else return half * half % t;
}

bool Miller_Rabin(ll x) {
  if(x == 1) return 0;
  ll div = x-1 , cnt = 0;
  while(!(div % 2)) div >>= 1 , ++cnt;
  Go(i , 0 , 6) {
    if(x == primelist[i]) return 1;
    ll fst = quickt(primelist[i] , div , x);
    Go(i , 1 , cnt){
      ll scd = fst * fst % x;
      if(scd == 1 && !(fst == 1%x || fst == (x-1)%x)) return 0;
      fst = scd;
    }
    if(fst != 1) return 0;
  }
  return 1;
}
int main() {
  ll n , m;
  scanf("%lld%lld" , &n , &m);
  while(m--) {
    ll x; scanf("%lld" , &x);
    puts(Miller_Rabin(x) ? "Yes":"No");
  }
  return 0;
}

$\text{GCD}$

下面有关于GCD的东西都会提一下。

$\text{GCD}$求法

如果$k|a,k|b$，那一定有$k|max(a,b)\bmod min(a,b)$，正确性可以画图来证。
这就是辗转相除法的原理：$gcd(a,b) = gcd(b , a\bmod b)$，边界为$gcd(x , 0) = x$
每次模一下数量级减少至少一倍，所以复杂度是$\mathcal{O(logn)}$.

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

当然，$C++$中自带的$\text{std::__gcd(a,b)}$也可以做到这一点，不过$NOIp$好像用不了。

$\text{ExGCD}$

$\text{Multiplicative Function}$

注意：接下来仅仅谈论数论函数，即定义域仅在正整数域的函数。
对于函数$f$：
如果对于任何的$(x,y) = 1,f(x)\times f(y) = f(xy)$，则称$f$函数为积性函数。
如果没有$(x,y)=1$的限制，即对于所有正整数对都满足如上条件，则称$f$函数为完全积性函数。

$\text{Phi’s Function}$
$\varphi(n)$表示$\leq n$且与$n$互质的数的个数。
公式化的描述，$\varphi(n)=\sum_{i=1}^{n}[(i,n)==1]$
怎么计算？
$\mathcal{O(\sqrt n)}:\text{Brute Force}$
考虑容斥。
我们发现一个数的$\varphi$一定只跟其质因子有关。于是就可以写出一个式子：

$\varphi(n) = n - (n / p_1) - (n / p_2) - ...+ (n / (p1 \times p2)) + ...$ $\varphi(n) = n(1 - p_1)(1 - p_2)...(1 - p_n)$

~~（其实就是硬拆上面那个式子得到的）~~
然后就可以枚举质因子硬乘就可以了。

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

$\text{Linear Sieve}$

考虑硬拆式子。
重温$\text{Euler Sieve}$的过程，就是找$n$的最小质因子$p_1$将其用$p_1 \times (n / p_1)$筛掉。
先设$n’ = n / p_1$，再分两种情况讨论：
$①:n’$有$p_1$这一因子。意味着唯一分解中$k_1 > 1$
那么显然，$n’$有着$n$的所有质因子。所以

$\begin{aligned} \varphi(n)&= n \prod\limits_{i = 1} ^ {n} \frac{p_i - 1}{p_i} \\ &= p_1 \times n' \prod\limits_{i = 1} ^ {n} \frac{p_i - 1}{p_i} \\ &= p_1 \times \varphi(n') \\ \end{aligned}$

$②:n’$没有$p_1$这一因子。意味着唯一分解中$k_1 = 1$

$\begin{aligned} \varphi(n)&= n \prod_{i = 1} ^ {n} \frac{p_i - 1}{p_i} \\ &= p_1 \times n' \times \frac{p_1-1}{p_1} \prod\limits_{i = 2} ^ {n} \frac{p_i - 1}{p_i} \\ &= (p_1-1) \times \varphi(n') \\ \end{aligned}$

（其实也证明了欧拉函数是积性函数）
愉快的筛就好了。注意任何积性函数都有$f(1) = 1$.

void Euler_Sieve(int x) {
  np[1] = 1; phi[1] = 1;
  Go(i , 2 , x) {
    if(!np[i]) prime[++cnt] = i , phi[i] = i - 1;
    for(int j = 1; j <= cnt && i * prime[j] <= x; j++) {
      np[i * prime[j]] = 1;
      if(i % prime[j])
        phi[i * prime[j]] = phi[i] * (prime[j] - 1);
      else  {
        phi[i * prime[j]] = prime[j] * phi[i];
        break;
      }
    }
  }
}

# 数论