【AcWing】 数学知识 听课笔记

数学知识 听课笔记"/>

【AcWing】 数学知识 听课笔记

ACwing数学知识听课笔记

• 质数
• 约数
• 欧拉函数
• 快速幂
• 扩展欧几里得算法
• 中国剩余定理
• 高斯消元
• 组合计数
• 容斥原理
• 简单博弈论

质数

试除法判定质数

bool is_prime(int n)
{if (n < 2) return false;for (int i = 2; i <= n / i; i ++)if (n % i == 0)return false;return true;
}

试除法分解质因数

#include<iostream>
#include<algorithm>using namespace std;void divide(int x)
{for (int i = 2; i <= x / i; i ++ )if (x % i == 0) //此处 i 一定是质数{int s = 0;while (x % i == 0) x /= i, s ++ ;cout << i << ' ' << s << endl;} 			//如果x没有除尽，转入下一个判断if (x > 1) cout << x << ' ' << 1 << endl;cout << endl;
}int main()
{int n;scanf("%d", &n);while (n -- ){int x;scanf("%d", &x);divide(x);}return 0;
}

普通筛法
#include<iostream>
#include<algorithm>using namespace std;const int N = 1000010;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;}
}
int main()
{int n;cin >> n;get_primes(n);cout << cnt << endl;return 0;
}//8
//4

埃氏筛法
#include<iostream>
#include<algorithm>using namespace std;const int N = 1000010;int primes[N], cnt;bool st[N];void get_primes(int n){for (int i = 2; i <= n; i ++){if (!st[i]){primes[cnt ++] = n;for (int j = i + i; j <= n; j += i) st[j] = true;}}}int main(){int n;cin >> n;get_primes(n);cout << cnt << endl;return 0;}

约数

欧拉函数

快速幂

扩展欧几里得算法

中国剩余定理

高斯消元

组合计数

容斥原理

简单博弈论