算法基础数论

因数和质因数分解

质数判断

复杂度：

#include <iostream>
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
const ll inf = 4e18, p = 998244353;

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

int main() {
  int n;
  cin >> n;
  cout << isprime(n);
}

分解因数

int main() {
  ll n;
  cin >> n;
  vector<ll> v;

  for (ll i=1;i*i<=n;++i) {
    if (n % i)
      continue;

    v.push_back(i);
    if (i != n/i) v.push_back(n/i);
  }
  sort(v.begin(), v.end());
  for (auto &i : v) {
    cout << i << ' ';
  }
}

质因数分解

int main() {
  ll n;
  cin >> n;
  vector<ll> v;
  for (ll i=2;i*i<=n;++i) {
    if (n % i)
      continue;
    v.push_back(i);
    // 除干净i logn
    while (n % i == 0) 
      n/=i;
  }
  if (n>1) v.push_back(n);
  sort(v.begin(), v.end());
  for (auto &i: v) {
    cout << i << ' ';
  }
}

素数筛

1、埃氏筛法

复杂度:
使用bitset记录下标是否为素数，如：
0代表下标是素数未被筛除，1代表不是素数被筛除。
b[0]=1，b[1]=1，b[2]=0，b[3]=0
2和3均为素数，将其倍数标记为筛除，继续遍历以此类推

#include <bitset>
#include <iostream>
using namespace std;
using ll = long long;
const int N = 2e6 + 10;

bitset<N> vis;

int main() {
  int n;
  cin >> n;
  vis[0] = vis[1] = 1;
  for (int i = 2; i <= n; ++i) {
    if (!vis[i])
	  // 从其最近的倍数开始，步长为i，筛掉i的倍数
	  // int j = i*i更好，2i会被2筛掉，3i会被3筛掉...
      for (int j = 2 * i; j <= n; j += i)
        vis[j] = 1;
  }
  for (int i = 1; i <= n; ++i)
    if (!vis[i])
      cout << i << ' ';
}

2、欧拉筛

一般埃氏筛能满足大多数要求，以后用到就补充。

GCD和LCM

唯一分解定理

自然数N可以唯一分解成几个数幂连乘的形式。

$N=P_1^{a_1} \times P_2^{a_2} \times \cdots \times P_m^{a_m}$

例如：

$\begin{align} A=&P_1^{a_1} \times P_2^{a_2} \times \cdots \times P_m^{a_m} \\\\ B=&P_1^{b_1} \times P_2^{b_2} \times \cdots \times P_n^{b_n} \\\\ 12 =& 2^2 \times 3^1 \times 7^0\\\\ 21 =& 2^0 \times 3^1 \times 7^1 \end{align}$

则

辗转相除法

已知

$a, b \in N, a\leq b, gcd(a, b) = gcd(a, b-a)$

则

若 右 小 于 左 交 换 位 置 若 右 侧 减 到 说 明

结合唯一分解定理则

$a\times b = gcd(a, b) \times lcm(a, b)$

代码实现gcd, lcm

ll gcd(ll a, ll b) {
	return b==0 ? a : gcd(b, a%b); 
}
ll lcm(ll a, ll b) {
	// a*b/gcd(a,b)可能会溢出long long
	return a/gcd(a, b) * b;
}

在numeric和万能头中也有实现,例如

#include <numeric>
// 或
#include <bits/stdc++.h>
...
int main() {
	cout << gcd(12, 21);
	cout << lcm(12, 21);
}

快速幂

复杂度:
求, 或其他在取模前会溢出的式子。
已知以下等式：

那么

$\begin{align} a^b=&a \times a \times a \cdots \times a \\\\ a^8=&(a^4)^2 = ((a^2)^2)^2 \\\\ a^{13} =&(a^6)^2 \times a \end{align} $$ 所以：$

a^b =

$实现： <figure class="highlight cpp"><table><tr><td class="gutter"><pre>1 2 3 4 5 6 7 8 9 10 </pre></td><td class="code"><pre>int qpow(int a, int b){ int ans = 1; while(b){ if(b&1) //如果n的当前末位为1 ans *= a; //ans乘上当前的a a *= a; //a自乘 b >>= 1; //n往右移一位 } return ans; } </pre></td></tr></table></figure> 如果需要模p <figure class="highlight cpp"><table><tr><td class="gutter"><pre>1 2 3 4 5 6 7 8 9 10 </pre></td><td class="code"><pre>ll qpow(ll a, ll b, ll c) { ll res = 1; while (b) { if (b & 1) res = res * a % c; a = a * a % c; // 右移会向下取整，会改变奇偶性 b >>= 1; } return res; } </pre></td></tr></table></figure> ## 乘法逆元 $(\frac{1}{a})\mod p = b$，那么a和b互为逆元。逆元可以用来计算以下算式： <div>$

(\frac{a \times b}{c}) \% p = (a \times b \times \frac{1}{c}) \% p = (a \times b \times inv(c)) \%p

$</div> $inv(c)$为c的逆元。使用**费马小定理**求逆元：对于一个素数P，始终有$

$例如：$

$实现： <figure class="highlight cpp"><table><tr><td class="gutter"><pre>1 2 3 </pre></td><td class="code"><pre>ll inv(ll x) { return qpow(x, p-2); } </pre></td></tr></table></figure> ## 欧拉定理 ### 欧拉函数$

\varphi(n) = \prod{i=1}^r p_i^{k_i-1} = \prod{p|n}p^{ \alphap-1} = n \prod{p|n}(1- \frac{1}{p})

$表示$[1, n]$中与n互质的数的个数。$\varphi(1)=1$ 欧拉定理：$

a^{\varphi(b)} \equiv 1 \mod b

$$
当b为素数就是费马小定理。