算法课
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
文章目录
- 质数：在大于1的整数中，如果只包含1和本身这两个约数，为质数，或者叫做素数。
- 约数
- 互质与欧拉函数
- 快速幂
- 欧几里得
- 博弈论入门
质数：在大于1的整数中，如果只包含1和本身这两个约数，为质数，或者叫做素数。
- 质数的判定——试除法: 时间复杂度:
参考：
约数
- 试除法求一个数的所有约数——一个数的约数是成对出现的：时间复杂度：
vector<int> get_divisor(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); //防止i*i为n，只要一个 } } sort(res.begin(), res.end()); return res; }- 约数个数
- 约数定理
- 最大公约数——欧几里得算法
/* a >= b 时成立 a < b && b != 0时 gcd(a, b) == gcd(b, a%b) == gcd(b, a)成立 */ int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }互质与欧拉函数
互质：除了1以外,没有其他公约数时，称这两个数为互质数.
欧拉函数：1～N中与N互质的数的个数- 公式求欧拉函数:时间复杂度：
int get_ola(int x) { int res = x; for(int i = 2; i <= x/i; ++i) { if(x % i == 0) { res = res / x * (x-1); //因为只按照公式直接干的话，直接乘会越界，但是先除就不会越界 while(x % i == 0) x /= i; } } if(x > 1) res = res / x * (x-1); cout<<res<<endl; }- 线性筛法求欧拉函数:时间复杂度：
LL get_ola(int n) { phi[1] = 1; for(int i = 2; i <= n; ++i) { if(!st[i]) { primes[cnt++] = i; phi[i] = i-1; //如果一个数i是质数的，其欧拉函数就是i-1个//1、 } for(int j = 0; primes[j] <= n/i; ++j) { st[primes[j]*i] = true; if(i % primes[j] == 0) //break; { phi[primes[j]*i] = primes[j]*phi[i]; // 2、 break; } else { // phi[primes[j]*i] = primes[j]*phi[i] / primes[j] * (primes[j]-1); phi[primes[j]*i] = phi[i] * (primes[j]-1); //3、 break; } } } LL res = 0; for(int i = 1; i <= n; ++i) res += phi[i]; return res; }参考：
874. 筛法求欧拉函数快速幂
- 快速幂——反复平方法：时间复杂度:
//反复平方法 int qmi(int a, int b, int p) { int res = 1; while(b) { if(b & 1) //检查个位 res = (LL)res*a%p; a = (LL)a*a%p; b >>= 1; //把b的个位删掉 } return res; }- 快速幂求逆元——欧拉定理、费马小定理
#include <iostream> using namespace std; typedef long long LL; int n; int a, b, p; //反复平方法 int qmi(int a, int b, int p) { int res = 1; while(b) { if(b & 1) //检查个位 res = (LL)res*a%p; a = (LL)a*a%p; b >>= 1; //把b的个位删掉 } return res; } int main() { cin>>n; while(n--) { cin>>a>>p; int res = qmi(a, p-2, p); if(a%p) cout<<res<<endl; else cout<<"impossible"<<endl; } return 0; } ```欧几里得
- 扩展欧几里得算法——裴蜀定理
int exgcd(int a, int b, int &x, int &y) //要求 { if(!b) { x = 1, y = 0; return a; } int d = exgcd(b, a%b, x, y); //已经求好 int z = x; x = y; y = z-y*(a/b); //得出参数的x、y return d; }- 线性同余方程——扩展欧几里得算法
typedef long long LL; int exgcd(int a, int b, int &x, int &y) //要求 { if(!b) { x = 1, y = 0; return a; } int d = exgcd(b, a%b, x, y); //已经求好 int z = x; x = y; y = z-y*(a/b); //得出参数的x、y return d; } int main() { int n; scanf("%d", &n); while(n--) { int a, b, m, x, y; scanf("%d%d%d", &a, &b, &m); int d = exgcd(a, m, x, y); if(b%d) printf("impossible\n"); else printf("%d\n", (LL)x*(b/d)%m); // 不可以写成x/d*b, 因为上面保证d能整除b，但不能保证d能整除x } return 0; }博弈论入门
- Nim游戏
#include <iostream> using namespace std; int n; int ans; int main() { cin>>n; int x; while(n--) { cin>>x; ans ^= x; } if(ans) cout<<"Yes"<<endl; else cout<<"No"<<endl; return 0; }- 集合——Nim游戏
#include <iostream> #include <cstring> #include <unordered_map> #include <algorithm> using namespace std; /* mex(S):不属于该集合S的最小非负整数 SG(终点) = 0 SG(X)从后往前求出来的 n个图(石子)的起点的SG值异或起来!=0 先手必胜 */ const int N = 110, M = 10010; int n, m; int s[N], f[M]; int sg(int x) //记忆化搜索 { if(f[x] != -1) return f[x]; unordered_set<int> S; for(int i = 0; i < m; ++i) { int sum = s[i]; if(x >= sum) S.insert(sg(x-sum)); } for(int i = 0; ; i++) if(!S.count(i)) return f[x] = i; } int main() { cin>>m; for(int i = 0; i < m; ++i) cin>>s[i]; cin>>n; memset(f, -1, sizeof(f)); for(int i = 0; i < n; ++i) { int x; cin>>x; res ^= sg(x); } if(res) puts("Yes"); else puts("No"); return 0; }阿里云国内75折 回扣 微信号：monov8 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 - 试除法求一个数的所有约数——一个数的约数是成对出现的：时间复杂度：