整除

b | a：表示b 整除 a，即b是a的因数（存在一个整数q ，使得a = qb）

素数

* 若 n 为合数，则n = ab 其中1 < a < n, 1 < b < n

定理

任何大于1的整数必有素因子

任何合数n都至少有一个不超过n^1/2的素因子

判断n是否为素数：如果所有小于n^1/2的素数p都不能整除n 则n为素数

int t = 2;
for (int i = 2; i * i <= x; ++i)
    if (x % i == 0) {
         t = i;
         break;
    }
if (x % t)
    t = x;

example

算术基本定理

任何非零整数n ，可以表示成如下乘积形式

n = p₁^k1p₂^{_^k²} ....p_n^kn其中p1，p2...pn 是互不相同的素数， k1，k2...kn是正整数

欧几里得定理
- 素数有无穷多个

模运算

*a mod b = r => a = qb + r

有关负数取模：

性质

(a + b) mod n = (a mod n + b mod n) mod n

(a - b) mod n = (a mod n - b mod n + n ) mod n // 减法运算时可能出现负数此时需要加上 n

(a * b) mod n = (a mod n * b mod n) mod n

**除法没有该种性质

每一步计算都可以取模最终结果不要忘了取模

最大公约数

a 与 b 的最大公约数为d 记作gcd (a , b) = d

gcd ( a , b ) = 1 => a b 互素

性质

设 gcd (a , b ) = d , a = q₁d b = q₂d 则 gcd( q₁ , q2 ) = 1

欧几里得算法

a = qb + r 则 gcd (a , b ) = gcd ( b, r ) （辗转相除法）

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

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

gcd

扩展欧几里得算法

　求不定方程 ax + by = gcd(a, b)

关于方程ax + by = k 给定a, b, k 的值 可以求出一组 x y 的解
 X = x * k / gcd(a, b)   
 Y = (k - a * x) / gcd(a, b)

int exgcd(int a, int b, int &x, int & y) {
    if (b == 0)  {
        x = 1;
        y = 0;
        return a;
     }
     int d = exgcd(b, a % b, x , y); 
     tie(x, y) = make_pair(y, x - a / b * y);
     return d;   // 返回值为是这组解(x, y)的最大公因数
}

exgcd

JZTXT

数学知识

整除

素数

模运算

最大公约数