参考yxc大佬的总结
最大公约数(欧几里得算法)
求两个正数的最大公约数，时间复杂度$O(logn)$.
C++ 版本代码
1
2
3
4
5
6
7
8
9
10
11
// 最大公约数 a>b
int gcd (int a, int b){
return b ? gcd(b, a % b) : a;
}
// 两个数的最小公倍数 * 两个数的最大公约数 = a*b a>b
// 最小公倍数
int lcm(int a, int b) {
return a * b / gcd(a, b);
}
扩展欧几里得算法
裴蜀定理：若a，b是整数，且(a, b) = d,即a,b的最大公约数是d，那么对于任意的整数x，y，$ax+by$都一定是d的倍数，特别地，一定存在x，y，使得ax+by=d成立。扩招欧几里得算法可以在$O(logn)$的时间复杂度内求出系数x，y。
C++ 版本代码
1
2
3
4
5
6
7
8
9
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;
}
判断一个数是否是素数
判断一个数是否是素数。
C++ 版本代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool isPrime(int num) { // 时间复杂度O(n)
for (int i = 2; i <= num; i++)
if (num % i == 0) return false;
return true;
}
/**
* 时间复杂度O(sqrt(n))
*/
bool isPrime(int num) {
for (int i = 2; i * i <= num; i++)
if (num % i == 0) return false;
return true;
}
线性筛素数
求从1到n的所有素数。
C++ 版本代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int countPrimes(int N) {
vector<bool> isPrime(N + 1, true);
// 判断一个数n是否是素数，只需要判断[1,sqrt(n)]中有没有可整除因子
for (int i = 2; i * i <= N; i++) {
if (isPrime[i]) {
// 如果当前值是素数，那么它的倍数肯定不是素数，注意这儿从平方开始
for (int j = i * i; j <= N; j += i) {
isPrime[j] = false;
}
}
}
int count = 0;
for (int i = 2; i <= N; i++) {
if (isPrime[i]) {
count++;
}
}
return count;
}
欧拉函数
欧拉函数，一般记为$\Phi (n)$,表示小于等于n的数中与n互质的数的个数。如果$n=p_1^{a_1}\times p_2^{a_2}\times … \times p_m^{a_m}$, 则$\Phi (n) = n(1-\frac{1}{p_1})…(1-\frac{1}{p_m})$
欧拉函数的常用性质：
- 如果n,m互质，则$\Phi (nm) = \Phi(n)\Phi(m)$;
- 小于等于n，且与n互质的数的和是$\Phi (n)\times n / 2$;
- 欧拉定理：如果n，a互质，且均为正整数，则$a^{\Phi(n)}=1(mod n)$
下面的代码可以在 $O(n)$ 的时间复杂度内求出 1∼n 中所有数的欧拉函数:
C++ 版本代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int primes[N], euler[N], cnt;
bool st[N];
// 质数存在primes[]中，euler[i] 表示
// i的欧拉函数
void get_eulers(int n){
euler[1] = 1;
for (int i = 2; i <= n; i ++ ){
if (!st[i]){
primes[cnt ++ ] = i;
euler[i] = i - 1;
}
for (int j = 0; primes[j] <= n / i; j ++ ){
st[primes[j] * i] = true;
if (i % primes[j] == 0){
euler[i * primes[j]] = euler[i] * primes[j];
break;
}
euler[i * primes[j]] = euler[i] * (primes[j] - 1);
}
}
}
判断分数是否为无限循环小数
已知分子a和分母b ，判断 分数a/b是否为无限循环小数。
已知结论：将分数化为最简分数后，分母的全部因数（除去1和其自身）没有为2或5以外的数，则该分数就不是无限循环小数；否则为无限循环小数。最简分数是否为无限循环小数，与分子没有关系。
C++ 版本代码
1
// 待填。。。
同余定理
同余定理：如果整数$a$和整数$b$满足$a-b$能够被$m$整除，即$(a-b)/m$是一个整数$(a-b)\%m==0$，则$a$对$m$取余与$b$对$m$取余相等，即$a\%m==b\%m$。
给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。LeeCode974 思路：如果两个数的差能被K整除，就说明这两个数 mod K得到的结果相同，只要找有多少对 mod k 相同的数就可以组合一下得到结果。 时间复杂度：$O(N)$，空间复杂度：$O(K)$.
C++ 版本代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int subarraysDivByK(vector<int>& A, int K) {
unordered_map<int, int> hash;
hash[0] = 1; // 元素单独可以被k整除
for (int i = 0; i < A.size(); i++) {
// 如果为负数时，需要转换为正数，这个转换原理，就是如果两个余数相加等于0，可以转换为相减等于0
A[i] = (((i == 0 ? 0 : A[i - 1]) + A[i]) % K + K) % K;
hash[A[i]]++;
}
int res = 0;
for (auto item : hash) {
res += item.second * (item.second - 1) / 2;
}
return res;
}
判断一个数是否是平方数
思路1：使用库函数
C++ 版本代码
1
2
3
4
bool isSqrt(int n){
int m = floor(sqrt(n));
return m * m == n;
}
思路2：二分法 时间复杂度：$O(log(n))$
C++ 版本代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
bool isSqrt(int n) {
int l = 1, r = n;
while (l <= r) {
int mid = (long)l + r >> 1;
if ((long)mid * mid == n)
return true;
else if ((long)mid * mid < n)
l = mid + 1;
else
r = mid - 1;
}
return false;
}
bool isSqrt2(int n) {
if (!n) return true;
int l = 1, r = n;
while (l < r) {
int mid = (long)l + r + 1 >> 1;
if ((long)mid * mid <= n)
l = mid;
else
r = mid - 1;
}
return l * l == n;
}
思路3：利用数学恒等式 $1+3+5+…+2n-1=n^2$ 时间复杂度：$O(\sqrt {n^2})$
C++ 版本代码
1
2
3
4
5
6
bool isSqrt(int n) {
for (int i = 1; n > 0; i += 2) {
n -= i;
}
return n == 0;
}
