质数
试除法判断质数 $ O(\sqrt{N}) $
1
2
3
4
5
6
7
8
| bool is_prime(int x)
{
if (x < 2) return false;
for (int i = 2; i <= x / i; i ++ )//写i*i<=x容易爆int,写i<=sqrt(x)太慢
if (x % i == 0)
return false;
return true;
}
|
试除法分解质因数 $ O(logN) -O(\sqrt{N}) $
1
2
3
4
5
6
7
8
9
10
11
12
| void divide(int x)
{
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
{
int s = 0;
while (x % i == 0) x /= i, s ++ ;
cout << i << ' ' << s << endl;
}
if (x > 1) cout << x << ' ' << 1 << endl;
cout << endl;
}
|
埃氏筛筛质数 $ O (N\sqrt{N}) $
原理：每次将i的倍数筛去
1
2
3
4
5
6
7
8
9
10
11
12
13
| int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (st[i]) continue;
primes[cnt ++ ] = i;
for (int j = i + i; j <= n; j += i)
st[j] = true;
}
}
|
质数筛 $ O(N) $
原理：保证每个数都是被其最小的质因数筛去
证明：
当 i%prime[j]==0时,由于质数从小到大枚举，因此prime[j]必定是i的最小质因数,也必定是i*prime[j]最小质因数 当i%prime[j]!=0时,也可以发现仍然为最小质因数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] <= n / i; j ++ )
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
|
试除法求所有约数 $ O(\sqrt{N}) $
1
2
3
4
5
6
7
8
9
10
11
12
| vector<int> get_divisors(int x)
{
vector<int> res;
for (int i = 1; i <= x / i; i ++ )
if (x % i == 0)
{
res.push_back(i);
if (i != x / i) res.push_back(x / i);
}
sort(res.begin(), res.end());
return res;
}
|
约数个数和约数之和
1
2
3
| 如果 N = p1^c1 * p2^c2 * ... *pk^ck
约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)
|
求约数之和
等比数列求和
复杂度：$ O(KlogN) $
分治做法
。。。。。。。。
欧几里得求GCD $ O(logN) $
1
2
3
4
| int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
|
求欧拉函数 $ O(\sqrt{N}) $
1
2
3
4
5
6
7
8
9
10
11
12
13
| int phi(int x)
{
int res = x;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
{
res = res / i * (i - 1);
while (x % i == 0) x /= i;
}
if (x > 1) res = res / x * (x - 1);
return res;
}
|
筛法求欧拉函数
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
27
28
29
30
31
32
33
34
35
36
37
38
39
| int primes[N], cnt; // primes[]存储所有素数
int euler[N]; // 存储每个数的欧拉函数
bool st[N]; // st[x]存储x是否被筛掉
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 ++ )
{
int t = primes[j] * i;
st[t] = true;
if (i % primes[j] == 0)
/*
prime[j]为i的质因子，
根据公式phi(N)=N*(1-1/p)*...,
只需改变N即N1=N*prime[j],
phi(N1)=phi(N)*prime[j]
*/
{
euler[t] = euler[i] * primes[j];
break;
}
/*
否则，N需要乘上prime[j]的同时，
还需乘上多一个质因子的贡献(1-1/prime[j])
即乘上prime[j]-1
*/
euler[t] = euler[i] * (primes[j] - 1);
}
}
}
|
欧拉定理
$ 若a与n互质，则有a^{\phi(n)} \equiv 1 (mod n) $
