一、质因子
??定义： 指能整除给定正整数的质数
??性质： 1没有质因子，每个正整数都能够以唯一的方式表示成它的质因数的乘积
??举例： 360 = 2 × 2 × 2 × 3 × 3 × 5 = 23 × 32 × 5，表示成了质因数乘积
时间复杂度： O(logn)，最坏为O( n \sqrt{n} n?)
算法思想： 从小到大枚举 n 的所有约数，假设枚举较小的那个 p，则 n 中最多只包含一个大于 n \sqrt{n} n? 的质因子，如果枚举结束，n 还大于1，那么说明这就是那个大于 n \sqrt{n} n? 的质因子，由性质的证明如下图。在筛质数的过程中，用的是欧式线性筛法
/**
* 例题1模板 - while循环下就是对应着它的性质
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5+10;
int primes[N];
int main(){
int n;
cin >> n;
for(int i = 2; i <= n; i++){
int t = i, j = 2;
while(t > 1)
if(t % j == 0) t /= j, primes[j]++;
else j++;
}
for(int i = 1; i <= 1e4; i++)
if(primes[i]) cout << i << " " << primes[i] << endl;
return 0;
}
?
二、质数
?定义： 一个正整数无法被除1和它自身以外的自然数整除则为质数
?性质： 任何一个大于1的自然数 n，如果 n 不为质数，那么 n 可以唯一分解成有限个质数的乘积，即 n =
P
1
α
1
?
P
2
α
2
?
P
3
α
3
?
?
?
P
k
α
k
P_{1}^{α_{1}} · P_{2}^{α_{2}} · P_{3}^{α_{3}} ··· P_{k}^{α_{k}}
P1α1???P2α2???P3α3?????Pkαk??，其中
P
1
<
P
2
<
?
?
?
<
P
k
P_{1} < P_{2} < ··· < P_{k}
P1?<P2?<???<Pk? 为质数，像
α
1
、
α
2
α_{1}、α_{2}
α1?、α2?之类的为次数
时间复杂度： 欧式筛法为O(n)，埃氏筛法为O(n·logn·logn)
说明： 欧式筛法是线性的，也是我们一般用得较多筛质数的方法。埃氏筛法用的较少，但是它的思路可以用于其他一些题目，思路比较重要
👉例题： 点这里
/**
* 欧拉线性筛质数
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 110, M = 1e5+10;
int n, cnt;
int nums[N], primes[M];
bool st[M*N];
int main(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> nums[i];
for(int i = 2; i <= M; i++){
if(!st[i]) primes[cnt++] = i;
for(int j = 0; primes[j] <= M/i; j++){
st[primes[j] * i] = true;
if(i % primes[j] == 0) break;
}
}
for(int i = 1; i <= n; i++)
if(!st[nums[i]] && nums[i] != 1) cout << nums[i] << " ";
return 0;
}
?
三、约数
?定义： 可表示为 N =
P
1
α
1
?
P
2
α
2
?
P
3
α
3
?
?
?
P
k
α
k
P_{1}^{α_{1}} · P_{2}^{α_{2}} · P_{3}^{α_{3}} ··· P_{k}^{α_{k}}
P1α1???P2α2???P3α3?????Pkαk??，使得 a 能被 b 整除，则 b 称为 a 的约数
?性质： 点这里参考性质，约数的性质很多都可以用质因数分解表示和解释
种类：
?① 试除法求一个数的所有约数，时间复杂度为 O( n \sqrt{n} n?)
?② 求约数个数，时间复杂度为 O( n \sqrt{n} n?)
?③ 求约数之和，时间复杂度为 O( n \sqrt{n} n?)
?④ 求最大公约数，时间复杂度为 O(logn)
① 试除法求一个数所有约数
#include <bits/stdc++.h>
using namespace std;
vector<int> get_diisors(int n){
vector<int> res;
for(int i = 1; i <= n / i; i++)
if(n % i == 0){
res.push_back(i);
if(i != n / i) res.push_back(n / i);
}
sort(res.begin(), res.end());
return res;
}
int main(){
int n;
whilen(n--){
int x;
cin >> x;
auto res = get_divisors(x);
for(auto t : res) cout << t << ' ';
cout << endl;
}
return 0;
}
?
② 求约数个数
约数个数为：
(
a
1
+
1
)
?
(
a
2
+
1
)
?
?
?
(
a
k
+
1
)
(a_{1} + 1)·(a_{2} + 1)···(a_{k} + 1)
(a1?+1)?(a2?+1)???(ak?+1)
/**
* 求约数个数
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e9+7;
int main(){
int n;
cin >> n;
unordered_map<int, int> primes;
while(n--){
int x, j = 2;
cin >> x;
while(x > 1)
if(x % j == 0) x /= j, primes[j]++;
else j++;
}
LL res = 1;
for(auto prime : primes)
res = res * (prime.second + 1) % mod;
cout << res << endl;
return 0;
}
③ 求约数和
约数之和为：
(
P
1
0
+
P
1
1
+
P
1
2
+
?
?
?
P
2
k
)
?
(
P
2
0
+
P
2
1
+
P
2
2
+
?
?
?
P
2
k
)
?
?
?
(
P
k
0
+
P
k
1
+
P
k
2
+
?
?
?
P
k
k
)
(P_{1}^0+P_{1}^1+P_{1}^2+ ··· P_{2}^k)·(P_{2}^0+P_{2}^1+P_{2}^2+ ··· P_{2}^k)···(P_{k}^0+P_{k}^1+P_{k}^2+ ··· P_{k}^k)
(P10?+P11?+P12?+???P2k?)?(P20?+P21?+P22?+???P2k?)???(Pk0?+Pk1?+Pk2?+???Pkk?)
/**
* 求约数之和
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e9+7;
int main(){
int n;
cin >> n;
unordered_map<int, int> primes;
while(n--){
int x, j = 2;
cin >> x;
while(x > 1)
if(x % j == 0) x /= j, primes[j]++;
else j++;
}
LL res = 1;
for(auto prime : primes){
int p = prime.first, a = prime.second;
// 令 t = 1，执行完一次后为 t = p+1
// 执行第二次为 t = p^2 + p + 1
// 执行 a 次后为 t = p^a + ··· + 1
LL t = 1;
while(a--) t = (t * p + 1) % mod;
res = res * t % mod;
}
cout << res << endl;
return 0;
}
?
④ 求最大公约数
<1> gcd辗转相除
我们一般用 gcd辗转相除法(欧几里得算法)，C++可以用STL自带两条下划线的 __gcd(int num1, int num2)，时间复杂度为O(logn)
问题思考：
? a) 基本性质是什么？
??一个数d，如果能实现 d/a、d/b，那么则会有 d/(a+b)、d/(ax+by)
? b) 若是两个数中最大公约数为1，输出的是什么？
??输出1
? c) 若其中有一个数为0或者两个数为0，又该输出什么？
??0与0没有最大公约数，除此之外0与其他数最大公约数为其他数本身
inline int gcd(int a, int b){
return b ? gcd(b, a % b) : a;
}
<2> 扩展欧几里得
定义： 在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数），使它们满足贝祖等式 a x + b y = g c d ( a , b ) ax + by = gcd(a, b) ax+by=gcd(a,b)
算法证明：
gcd(a, b) = d = ax + by，则有 b ? x ′ + ( a ?? m o d ?? b ) ? y ′ = d b·{x}' + (a\space \space mod\space \space b)·{y}' = d b?x′+(a??mod??b)?y′=d
a ?? m o d ?? b = a ? [ a b ] ? b a\space \space mod \space \space b = a - [\frac{a}{b} ]·b a??mod??b=a?[ba?]?b
b ? x ′ + ( a ? [ a b ] b ) ? y ′ = d b·{x}' + (a - [\frac{a}{b} ]b)·{y}' = d b?x′+(a?[ba?]b)?y′=d
移项得 a ? y ′ + b ( x ′ ? [ a b ] y ′ ) ? = d a·{y}' + b({x}' - [\frac{a}{b} ]{y}')· = d a?y′+b(x′?[ba?]y′)?=d
所以有 { x = y ′ y = x ′ ? [ a b ] y ′ \left\{\begin{matrix} x = {y}'\\y = {x}' - [\frac{a}{b} ]{y}'\end{matrix}\right. {x=y′y=x′?[ba?]y′?
当我们在计算exgcd的时候(如下代码)，将x和y翻转一下，便能更好的计算
则有： a ? x ′ + b ( y ′ ? [ a b ] x ′ ) ? = d a·{x}' + b({y}' - [\frac{a}{b} ]{x}')· = d a?x′+b(y′?[ba?]x′)?=d
所以有 { x = x ′ y = y ′ ? [ a b ] x ′ \left\{\begin{matrix} x = {x}'\\y = {y}' - [\frac{a}{b} ]{x}'\end{matrix}\right. {x=x′y=y′?[ba?]x′?
👇例题
#include <bits/stdc++.h>
using namespace std;
int exgcd(int a, int b, int& x, int& y){
if(!b){
x = 1, y = 0;
//a×1 + 0×0 = a
return a;
}
//注意这里翻转了y x 有利于后面转换y的时候式子运算
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
int main(){
int n;
scanf("%d", &n);
while(n--){
int a, b, x, y;
scanf("%d%d", &a, &b);
exgcd(a, b, x, y);
printf("%d %d\n", x, y);
}
return 0;
}
?
四、余数
?定义： 余数是整数，指整数除法中被除数未被除尽部分
?应用： 常用于对大数取模、数字拼接、取个位数等等
👉例题： 点这里
?
五、快速幂
?时间复杂度： O(logn)
/**
* 快速幂模板
*/
const int p = 1e9 + 7;
inline int qp(int x, int y){
int res = 1;
for(int i = x; y; y>>=1, i=i*i%p)
if(y & 1) res = res*i%p;
return res;
}
?
路漫漫其修远兮，吾将上下而求索