同余定理
同余定理：两个整数同时除以一个整数得到的余数相同，则二整数同余。记作a ≡ b(mod m)。
- 对于同一个除数，两个数之和（或差）与它们的余数之和（或差）同余。
- 对于同一个除数，两个数的乘积与它们余数的乘积同余。
- 对于同一个除数，如果有两个整数同余，那么它们的差就一 定能被这个除数整除。
- 对于同一个除数，如果两个数同余，那么他们的乘方仍然同余。
同余定理的加法乘法应用:
(a + b) % m = (a % m + b % m) % m
(a - b) % m = (a % m - b % m + m) % m
(a * b) % m = ((a % m) * (b % m)) % m
(a ^ b) % m = ((a % m) ^ b) % m
证明式一：
设 a = k1 * m + r1，b = k2 * m + r2
则 (a + b) % m = ((k1 * m + r1) + (k2 * m + r2)) % m
= ((k1 + k2) * m + (r1 + r2)) % m
= (r1 + r2) % m
= (a % m + b % m) % m
证明式二：
设 a = k1 * m + r1，b = k2 * m + r2
则 (a * b) % m = ((k1 * m + r1) * (k2 * m + r2)) % m
= (k1 * k2 * m^2 + (k1 * r2 + k2 * r1) * m + r1 * r2) % m
= (r1 * r2) % m
= ((a % m) * (b % m)) % m
高精度求模法和快速幂取模都是利用了同余定理。
// 高精度求模法
int mod(string a, int b) //高精度 a 除以单精度 b
{
int d = 0;
for (int i = 0; i < a.size(); i++)
d = (d * 10 + (a[i] - '0')) % b; //求出余数
return d;
}
快速幂算法是利用分治法在 O(logN) 的时间复杂度内求出 整数 X 的 N 次方 的值的算法。
算法原理为：
x^2n = (x*x)^n
x^(2n+1) = x * x^2n = x * (x*x)^n
2n 次乘法变成 n+1 次乘法（x*x 的结果可以保存下来，不用反复计算），而 2n+1 次乘法变成 n+2 次乘法（奇数次多出来的一个乘法单独计算）。
迭代实现如下：
int qpow(int x, int n) {
int res = 1;
while (n) { // 进行快速幂运算，n 为当前的指数值，n 为 0 的时候运算结束
if (n & 1) { // 用位运算的方式判断 n 是否为奇数，速度更快，等价于 n % 2
res *= x; // 如果 n 是奇数，那么需要将 x 存入运算结果中
}
x *= x;
n >>= 1; // 用位运算的方式进行 n/2，速度更快，等价于 n /= 2
}
return res;
}
数据太大时，64 位甚至 128 位的整型都无法表示，因此在这个基础上加上取余运算。
int qpow(int x, int n) {
int res = 1;
while (n) {
if (n & 1) {
res = res * x % m; // 有乘法的地方取余
}
x = x * x % m; // 有乘法的地方取余
n >>= 1;
}
return res;
}
递归实现很简单（最推荐）：
int qpow(int x, int n, int m) {
if (n == 0) {
return 1;
}
return qpow(x * x % m, n >>> 1) * (n % 2 == 0 ? 1 : x) % m;
}
x 的平方根
前面讲了快速幂，现在讲讲开平方根。
但是结果只保留整数的部分，小数部分将被舍去。
由于 x 平方根的整数部分是满足 k^2 <= x 的最大 k 值，
因此我们可以对 k 进行二分查找，从而得到答案。
二分查找的下界为 0，上界可以粗略地设定为 x。
def sqrt(x: int) -> int:
l, r, ans = 0, x, -1
while l <= r:
mid = (l + r) // 2
if mid * mid <= x:
ans = mid
l = mid + 1
else:
r = mid - 1
return ans
数位操作
// 把给定的数字分成指定位数的数组
// INPUT: 14458, num[5]
// OUTPUT: num[5]{8,5,4,4,1}
public static void numToArray(int number, int[] num) {
for (int i = 0; i < num.length; i++) {
num[i] = number % 10;
number /= 10;
}
}
// 把给定的数组变成数字
// INPUT: num[5]{8,5,4,4,1}
// OUTPUT: 14458, num[5]
public static int arrayToNum(int[] num) {
int n;
for (int i = 0; i < num.length; i++) {
n = n * 10 + num[i];
}
return n;
}
注意在上面的操作中如果把 10 换成其他基数，即可实现数字与其他进制各位数数组间转换：
def num_to_array(num: int, base: int) -> List[int]:
ans = []
while num != 0:
ans.append(num % base)
num //= base
return ans[::-1] if ans else [0]
其他进制各位数数组转十进制数字同理。
看下面这个实例 5681. 判断一个数字是否可以表示成三的幂的和：
给你一个整数 n ，如果你可以将 n 表示成若干个不同的三的幂之和，请你返回 true ，否则请返回 false 。
对于一个整数 y ，如果存在整数 x 满足 y == 3x ，我们称这个整数 y 是三的幂。
示例 1：
输入：n = 12
输出：true
解释：12 = 31 + 32
示例 2：
输入：n = 91
输出：true
解释：91 = 30 + 32 + 34
示例 3：
输入：n = 21
输出：false
提示：
1 <= n <= 107
要判断 n 能否表示成若干个不同的三的幂之和，不妨把其用三进制数表示。不难发现：
12 -> 0 * 3^0 + 1 * 3^1 + 1 * 3^2 -> 110(base 3) -> true
91 -> 1 * 3^0 + 0 * 3^1 + 1 * 3^2 + 0 * 3^3 + 1 * 3^4 -> 10101(base 3) -> true
21 -> 0 * 3^0 + 1 * 3^1 + 2 * 3^2 -> 210(base 3) -> false
如果某一位出现 2 说明重复使用了某个三的幂，则不满足要求。
function checkPowersOfThree(n: number): boolean {
while(n) {
if (n % 3 === 2) return false;
n = Math.floor(n / 3);
}
return true;
};
最小公约数与最小公倍数
// 求a,b的最小公约数，利用辗转相除法，其实是利用定理 gcd(a, b) == gcd(b, a % b)
// 由此可以递归，边界是 gcd(a, 0) == a
public static int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
// 求a,b的最小公倍数，利用上面求到的最小公约数 d，
// lcm = (a * b) / d，为了防止 a*b 溢出，写成 (a / d) * d
public static int lcm(int a, int b) {
return a / gcd(a, b) * b;
}
分数
// 分数，保存分子分母，方便起见，使用假分数
class Fraction {
int up, down;
// 化简，使其满足三个条件：
// 1. 分母始终为正数
// 2. 如果分子是0，则分母是1
// 3. 分子分母最小公约数是1
public void reduction() {
if (down < 0) {
down = -down;
up = -up;
}
if (up == 0) {
down = 1;
} else {
// 记得取绝对值
int d = gcd(Math.abs(up), Math.abs(down));
up /= d;
down /= d;
}
}
// 分数的除法，加减乘同理，返回自己，方便链式调用
public Fraction dividedBy(Fraction f) {
up *= f.down;
down *= f.up;
// 结果记得化简
reduction();
return this;
}
// 输出分三种情况：
// 1. 如果分母为1，则是整数，只输出分子
// 2. 如果分子绝对值大于分母，则是假分数，可以选择按带分数形式输出
// 3. 其他情况，是真分数直接输出
public void print() {
reduction(); // 记得先化简
if (down == 1) {
System.out.print(up);
} else if (Math.abs(up) > down) {
// 注意比较和输出分子时都要取绝对值
System.out.printf("%d %d/%d", up / down, Math.abs(up) % down, down);
} else {
System.out.printf("%d/%d", up, down);
}
}
}
素数
// 判断一个数是不是素数，注意1既不是素数又不是合数，因子只需要判断到这个数的开方
public static boolean isPrime(int n) {
if (n <= 1) {
return false;
}
int sqr = (int) Math.sqrt(n * 1.0);// 变量外提，强制类型转换，以优化循环速度
for (int i = 2; i <= sqr; i++) { // 从2开始判断，注意i<=sqr含有等号
if (n % i == 0) {
return false;
}
}
// 实践中，如果n比较小（10的9次方之内），可以简单的这样写
// for(int i = 2; i * i <=n; i++){
// if(n % i == 0)
// return false;
// }
return true;
}
// 获取一张直到给定数的素数表，从小数字开始，每发现一个素数，就向后筛去这个素数的整倍数
public static ArrayList<Integer> getPrimeList(int max) {
// 带标记表的方法
boolean[] mark = new boolean[max + 1]; // 偏移1个单位，使索引与数字对应
ArrayList<Integer> primes = new ArrayList<>();
for (int i = 2; i <= max; i++) { // 从2开始
if (!mark[i]) { // 注意，标记为false即是素数，否则不做任何处理
primes.add(i);
for (int j = i + 1; j <= max; j += i) { // 从i+1开始向后筛去整倍数，步进是i
mark[j] = true;
}
}
}
return primes;
}
均值不等式
剑指 Offer 14- I. 剪绳子
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
示例 1：
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
提示：
2 <= n <= 58
根据均值不等式可得推论一：将绳子以相等的长度等分为多段，得到的乘积最大。 通过实际求极值可得推论二：尽可能将绳子以长度 3 等分为多段时，乘积最大。 推导过程见 jyd 的 LeetCode 解答。 最后可得切分规则：
把绳子尽可能切为多个长度为 3 的片段，留下的最后一段绳子的长度可能为 0, 1, 2 三种情况：
若最后一段绳子长度为 0，即绳子总长度为 3 的整倍数，最优；
若最后一段绳子长度为 1，则应把一份 3 + 1 替换为 2 + 2，因为 2 × 2 > 3 × 1；
若最后一段绳子长度为 2，则保留，不再拆为 1 + 1。
实现为：
import math
class Solution:
def cuttingRope(self, n: int) -> int:
if n <= 3:
return n - 1
left = n % 3
if left == 1:
return int(math.pow(3, n // 3 - 1)) * 4
else:
return int(math.pow(3, n // 3)) * (1 if left == 0 else 2)
参考：
最后附上 GitHub：https://github.com/gonearewe
