数论学习笔记

概念不说了。

同余方程

同余方程基本形式：$ax\equiv c(\text{mod}\space b)$。

$ax\equiv c(\text{mod}\space b)\Longleftrightarrow \exists y\in \mathbb{Z},s.t. ax+by=c$

$ax+by=c$ 就可以用扩展欧几里得来求。

代码：

int exgcd (int a, int b, int& x, int& y) {
  if (!b) {
    x = 1, y = 0;
    return a;
  }
  int d = exgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}

乘法逆元

若 $ax\equiv 1(\text{mod}\space p)$，并且 $(a,p)=1$，则称 $a$ 与 $x$ 在 $\text{mod}\space p$ 下互为逆元，$x=\text{inv}(a)$。

求解乘法逆元的方法：

1. 扩欧，相当于 解 $ax\equiv 1(\mod\space p)$。适合求某一个数的逆元。
2. 费马小定理，若 $p$ 是质数，且 $(a,p)=1$，则 $a^{p-1}\equiv 1(\text{mod} p)$，那么 $\text{inv}(a)=a^{p-2}$。适用于 $p$ 为质数的情况。
3. 线性递推求逆元，适合求 $1\sim n$ 的逆元。

$$设\space p=aq+r,q=\bigg\lfloor\dfrac{p}{a}\bigg\rfloor，r=p\bmod a\\ \begin{aligned} aq+r&\equiv 0(\text{mod}\space p)\\ aq&\equiv -r(\text{mod}\space p)\\ a&\equiv -r\cdot \text{inv}(q)(\text{mod}\space p)\\ \text{inv}(a)&\equiv -q\cdot \text{inv}(r)(\text{mod}\space p)\\ \end{aligned}\\ 那么\space \text{inv}[a]=-\bigg\lfloor\dfrac{p}{a}\bigg\rfloor\cdot \text{inv}[p\bmod a]$$

总之，我觉得要求单个的逆元就用扩欧，多个的逆元就用线性递推，费马小定理随便。

中国剩余定理

这里直接讲扩展中国剩余定理。

定义：线性同余方程组，不要求模数两两互质。

$$\begin{cases} p_1\equiv a_1(\text{mod}\space m_1)\\ p_2\equiv a_2(\text{mod}\space m_2)\\ \space\space\space\space\space \space\vdots\\ p_n\equiv a_n(\text{mod}\space m_n)\\ \end{cases}$$

就是求这个方程的一个解。

解法

采用数学归纳法。

1. 假设前 $k-1$ 个方程的特解为 $x$，那么通解为 $x+t\cdot M$，其中 $M=\text{lcm}(m_1,m_2,\dots,m_{k-1})$。
2. 求解 $t$，使得 $x+t\cdot M\equiv a_k(\text{mod}\space m_k)$。
3. exgcd 判断是否有解，若有解，则 $x\gets x+t\cdot M$。

代码：

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int kMaxN = 1e5 + 5;

int n, a[kMaxN], b[kMaxN];
int M = 1;
__int128 res, x, y;

__int128 mod (__int128 x, __int128 m) {
  return (x % m + m) % m;
}

__int128 add (__int128 x, __int128 y, __int128 m) {
  return (x + y >= m) ? (x + y - m) : (x + y);
}

__int128 times (__int128 x, __int128 y, __int128 m) {
  return 1ll * x * y % m;
}

__int128 gcd (__int128 m, __int128 n) {
  return (!n) ? m : gcd(n, m % n);
}

__int128 lcm (__int128 m, __int128 n) {
  return m / gcd(m, n) * n;
}

__int128 exgcd (__int128 a, __int128 b, __int128& x, __int128& y) {
  if (!b) {
    x = 1, y = 0;
    return a;
  }
  __int128 d = exgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}

__int128 inv (__int128 a, __int128 m) {
  __int128 x, y;
  exgcd(a, m, x, y);
  return mod(x, m);
} 

signed main() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i] >> b[i];
  }
  res = b[1], M = a[1];
  for (int i = 2; i <= n; ++i) {
    __int128 s = mod(b[i] - mod(res, a[i]), a[i]);
    __int128 d = exgcd(M, a[i], x, y);
    __int128 m = M;
    M = lcm(M, a[i]);
    x = mod(times(x, s / d, a[i]), a[i]);
//    cout << "***" << i << ' ' << res << endl;
    res += times(x, m, M);
    res = mod(res, M);
  }
//  cout << exgcd(4, 48, x, y) << endl;
  cout << (long long)res << endl;
  return 0;
}

欧拉函数

对于 $n\in \mathbb{Z}^{+}$，$\varphi(n)$ 表示 $1\sim n$ 中与 $n$ 互质的正整数个数。

• 性质一：若 $p$ 是质数，$\varphi(p^{n})=p^{n-1}\cdot(p-1)$。
• 性质二：若 $a|x$，$\varphi(ax)=a\cdot\varphi(x)$。
• 性质三：若 $(a,b)=1$，$\varphi(ab)=\varphi(a)\cdot \varphi(b)$。

公式：

$$\text{If}\space n=\prod_{i=1}^{k}{p_i^{\alpha_i}}, \text{then}\space \varphi(n)=n\cdot\prod_{i=1}^{k}\dfrac{p_{i}-1}{p_{i}}$$

欧拉定理

若 $(a,m)=1$，$a^{\varphi(m)}\equiv 1(\text{mod}\space m)$。

推论：$a^b\equiv a^{b\bmod \varphi(m)}(\text{mod}\space m)$。

若 $b\geq \varphi(m)$，则 $a^b\equiv a^{b\bmod\varphi(m)+\varphi(m)}(\text{mod}\space m)$。