数论
1. 质数
1. 试除法判定质数
- 朴素解法:
O(n)
从2
枚举到n - 1
,看中间是否有数可以整除n
,可以则是质数,否则就不是质数
-
优化做法:
O(sqrt(n))
-
如果
n % d == 0
,那么显而易见n % (n / d) == 0
也是成立的。 - 由于枚举的时候,是从小到大枚举,因此
n <= (n / d)
成立,那么可以得出d^2 <= n
- 枚举的时候只需要枚举到
sqrt(n)
即可
bool check_prime_(int x) {
if (x < 2)return false;
for (int i = 2; i < x; i++) {
if (x % i == 0)return false;
}
return true;
}
// 优化做法
bool check_prime(int x) {
if (x < 2)return false;
for (int i = 2; i <= x / i; i++) {
if (x % i == 0)return false;
}
return true;
}
2. 分解质因数
-
数学性质
-
根据算数定理:任何一个数都可以写成
x = p1^a1 + p2^a2 + ... + pn^an
的形式,其中p
打头的是质数 -
任何一个数都只会有一个
>= sqrt(x)
的质因子,由反证法知,如果多于1
一个这样的质因子,那他们的乘积将大于x
。 -
算法
-
朴素解法:
O(n)
枚举
2~n
,计算质因子及其指数(注意:这种枚举方式中,会把合数筛除,比如
16
是2
的倍数,也是4
的倍数,但是由于是从小到大枚举,因此枚举到4
的时候,数中已经不包含2
的所有倍数了,因此不会吧4
计算到质因子中,对于其他质因子
同理) -
优化解法:
O(sqrt(n))
到
sqrt(x)
,当最后x>1
成立,则说明x
就是那个>sqrt(n)
的质因子
void prime_factors(int x) {
for (int i = 2; i <= x / i; i++) {
if (x % i == 0) {
int cnt = 0;
while (x % i == 0) {
x /= i;
cnt++;
}
printf("%d %d\n", i, cnt);
}
}
if (x > 1)printf("%d %d\n", x, 1);
}
3. 筛质数
- 埃氏筛法:
O(nlog(log(n)))
- 从
2
枚举到n
,枚举到未被标记的数,记录为质数,并且标记所有该数的倍数
void get_primes_normal(int x) {
bool st[x + 1];
int factors[x + 1], cnt = 0;
memset(st, false, sizeof st);
for (int i = 2; i <= x; i++) {
if (st[i])continue;
factors[cnt++] = i;
for (int j = i + i; j <= x; j += i)
st[j] = true;
}
printf("%d\n", cnt);
}
- 线性筛法:
O(n)
- 每个
0~x
之间的合数,都只会被其最小的质因子筛掉 - 核心代码中,由于质数是从小到大枚举的
- 当
i % primse[j] == 0
成立的时候,primes[j]
一定是i
的最小质因子,primes[j]
也一定是primes[j]*i
的最小质因子 - 当上面的条件不成立的时候,
primes[j]
一定比i
中的所有质因子小
- 当
void get_primes_linear(int x) {
// 初始化
bool st[x + 1];
int primes[x + 1], cnt = 0;
memset(st, false, sizeof st);
for (int i = 2; i <= x; i++) {
// 未被标记的数,是质数
if (!st[i])primes[cnt++] = i;
// 从较小的质数开始枚举
for (int j = 0; primes[j] <= x / i; j++) {
st[i * primes[j]] = true;
// 下面情况成立的时候,primes[j]一定是i的最小质因子,primes[j]也一定是primes[j]*i的最小质因子
// 当上面的条件不成立的时候,`primes[j]`一定比`i`中的所有质因子小
if (i % primes[j] == 0)break;
}
}
printf("%d\n", cnt);
}
2. 约数
1. 试除法求约数
- 算法思路:
- 从
1~sqrt(n)
,依次枚举,计算约数 - 当
n % i == 0
的时候,说明n / i
也是你n
的约数
void get_divisor(int x) {
vector<int> divisors;
for (int i = 1; i <= x / i; i++) {
if (x % i == 0) {
divisors.emplace_back(i);
if (i != x / i)divisors.emplace_back(x / i);
}
}
sort(divisors.begin(), divisors.end());
for (const auto &item : divisors)printf("%d ", item);
cout << endl;
}
2. 约数个数
- 数学定理:
- 根据算数定理:任何一个数都可以写成
x = p1^a1 + p2^a2 + ... + pn^an
的形式,其中p
打头的是质数 - 那么他的约数可以表示为
d=p1^b1 + p2^b2 + ... + pn^bn
,其中0 <= bi <= ai
- 根据排列组合定理,这个数的所有约数就是对应质因子指数的排列组合总数,即
(a1+1)*(a2+1)* ... *(an+1)
const int MOD = 1e9 + 7;
unordered_map<int, int> primes;
// 求数组中所有数的乘积的约数个数
void divisors_cnt(vector<int> &nums) {
for (auto num : nums) {
for (int i = 2; i <= num / i; i++) {
if (num % i != 0)continue;
while (num % i == 0) {
num /= i;
primes[i]++;
}
}
if (num > 1)primes[num]++;
}
long long res = 1;
for (const auto &item : primes) {
res = res * (item.second + 1) % MOD;
}
cout << res << endl;
}
3. 约数之和
- 数学定理
- 同上
- 约数之和可以表示为
d=p1^b1 + p2^b2 + ... + pn^bn
,其中0 <= bi <= ai
的和 - 把上面的式子合并过后就是
(p1^0+p1^2+...+p1^a1)*(p2^0+p2^2+...+p2^a2)*...*(pn^0+pn^2+...+pn^an)
const int MOD = 1e9 + 7;
unordered_map<int, int> primes;
void divisors_sum(vector<int> &nums) {
for (auto num : nums) {
for (int i = 2; i <= num / i; i++) {
if (num % i != 0)continue;
while (num % i == 0) {
num /= i;
primes[i]++;
}
}
if (num > 1)primes[num]++;
}
long long res = 1;
for (const auto &item : primes) {
long long t = 1;
int p = item.first, cnt = item.second;
for (int i = 1; i <= cnt; i++) {
t = (p * t + 1) % MOD;
}
res = res * t % MOD;
}
cout << res << endl;
}
4. 最大公约数
- 数学定理:
- 如果
x % d == 0 y % d == 0
, 那么(a*x + b*y) % d == 0
也是成立的 - 假设
x y
两个数,则x % y == x - [x / y] * y
,[]
表示的取整,由于x y
已知,那么[x / y]
可以看做常数c
,即x % y == x - c * y
- 由第一条可知,
x % d == 0 y % d == 0
时(x % y) % d == 0
也成立 - 算法:辗转相除法
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
3. 欧拉函数
1. 欧拉函数
- 定义:设一个数
N
的欧拉函数记为phi[N]
,其表达的含义是数N
以内所有和N
互质的数的个数(不包含N
) - 公式:设
p1 p2 p3 .. px
表示的N
所有的质因子,那么phi[N] = N * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/px)
- 证明:容斥定理
int euler(int x) {
int res = x;
for (int i = 2; i <= x / i; i++) {
if (x % i == 0) {
while (x % i == 0) {
x /= i;
}
res = res - res / i;
}
}
if (x > 1)res = res - res / x;
return res;
}
2. 筛法求欧拉函数
- 题目:求某一个数范围内所有数的欧拉函数
- 解题:基于动态规划思想和线性筛质数法求取答案
const int range = 1000010;
int phi[range];
bool st[range];
long long euler_sum(int x) {
vector<int> primes;
phi[1] = 1;
memset(st, false, sizeof st);
for (int i = 2; i <= x; i++) {
// 一个数 i 如果是质数,那么它的欧拉函数的值是 i - 1
if (!st[i]) {
phi[i] = i - 1;
primes.emplace_back(i);
}
for (int j = 0; primes[j] <= x / i; j++) {
st[i * primes[j]] = true;
if (i % primes[j] == 0) {
phi[i * primes[j]] = phi[i] * primes[j];
break;
}
phi[i * primes[j]] = phi[i] * (primes[j] - 1);
}
}
long long res = 0;
for (int i = 1; i <= x; i++)res += phi[i];
return res;
}
3. 欧拉定理
- 整数
和
除以
的余数相同,则称
模
同余,计作
- 定理 :设
,且
,则我们有:
4. 快速幂
1. 快速幂
-
场景:求
a
的k
次方模上p
的值 -
算法思路:一个数可以用二进制表示,因此只需要列出二进制表示中
bit
位为1
的幂方结果即可。相邻的的数bit
对应的幂方数值相差一个平方,求取很简单。
typedef long long ll;
ll qmi(ll a, ll k, ll p) {
ll res = 1;
while (k != 0) {
if ((k & 1) == 1) {
res = res * a % p;
}
a = a * a % p;
k >>= 1;
}
return res;
}
2. 快速幂求逆元
if (a % p == 0)printf("impossible\n");
else printf("%lld\n", qmi(a, p - 2, p));
5. 扩展欧几里得函数
1. 扩展欧几里得算法
int ex_gcd(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
int x1, y1;
int gcd = ex_gcd(b, a % b, x1, y1);
x = y1, y = x1 - a / b * y1;
return gcd;
}
2. 线性同余方程
int gcd = ex_gcd(a, a, x, y);
if (b % gcd != 0)printf("impossible\n");
else printf("%d\n", (long long) x * b / gcd % a);
6. 中国剩余定理
1. 线性同余方程组
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ex_gcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
ll x1, y1;
ll d = ex_gcd(b, a % b, x1, y1);
x = y1, y = x1 - a / b * y1;
return d;
}
int main() {
int n;
cin >> n;
// x是方程的解 a1 m1是参数
ll x, a1, m1;
cin >> a1 >> m1;
while (--n != 0) {
ll a2, m2;
cin >> a2 >> m2;
ll k1, k2;
ll d = ex_gcd(a1, a2, k1, k2);
if ((m2 - m1) % d != 0) {
cout << -1 << endl;
return 0;
}
k1 = k1 * (m2 - m1) / d;
// 把k1变成一个尽可能小的正数
ll mod = abs(a2 / d);
k1 = (k1 % mod + mod) % mod;
m1 = m1 + k1 * a1;
a1 = abs(a1 * a2 / d);
}
cout << m1 << endl;
x = (m1 % a1 + a1) % a1;
cout << x << endl;
return 0;
}