数学总结
论 数学
1.快速幂
快速幂算法是一种用于快速计算幂运算的算法，其时间复杂度为
快速幂算法通过将指数二进制的每一位与底数相乘来减少运算次数。例如，计算
快速幂算法可以通过多种方式实现，包括：
- 循环实现：通过循环遍历指数的二进制表示，逐位与底数相乘。
- 递归实现：将指数分成两半，递归计算一半的幂，然后根据指数的奇偶性决定是否乘以底数。
- 位运算实现：使用位运算判断指数的奇偶性，并逐步减少指数的值。
见此
int pow( int a, int b ) { int r = 1, base = a; while( b != 0 ) { if( b & 1 ) r *= base; base *= base; b >>= 1; } return r; }P1226
2质数筛
基本定义及性质：
质数又称素数。一个大于
在整个自然数集合中，质数的数量不多，分布比较稀疏，对于一个足够大的整数N，不超过N的质数大约有
质数的判断：
有一个简单而又暴力的算法，即试除法， 即扫描
伪代码如下:
bool is_prime(int n)
{
if(n < 2) return false;
for(int i = 2;i <= sqrt(n);i++)
if(n%i == 0) return false;
return true;
} 时间复杂度为：
有一些效率更高的随机性算法，不过水平超出了我们的范畴，不再讨论。
质数的筛选：
质数的筛法有许多种，先来介绍一个最实惠常用的埃拉托色尼斯筛法吧。
我们可以从2开始， 由小到大扫描每个数x，它的倍数 2x，3x，....，[N/x] * x 标记为合数。
当扫描到一个数时，若它尚未被标记，则它不能被2~x - 1之间的任何数整除，该数就是质数。
伪代码如下：
void primes(int n)
{
memset(vis, 0, sizeof(vis));
for(int i = 2;i <= n;i++)
{
if(vis[i]) continue;
printf("%d\n", i); //i是质数
for(int j = i;j <= n/i;j++) vis[i*j] = 1;
}
} 时间复杂度为：
该算法实现简单，效率已经非常接近于线性，是算法竞赛中最常用的质数筛法。
再来介绍一种更优的算法：线性筛（欧拉筛法）
算法思想：通过从大到小累积质因子的方式标记每个合数，设数组
1.依次考虑
2.若
3.扫描不大于
伪代码如下：
void primes(int n)
{
memset(v, 0, sizeof(v));//最小质因子
int m = 0;//质数数量
for(int i = 2;i <= n;i++)
{
if(v[i] == 0)
{
v[i] = i;
prime[++m] = i;//i是质数
}
//给当前的数i乘上一个质因子
for(int j = 1;j <= m;j++)
{
// i有比prime[j]更小的质因子,或者超出n的范围,停止循环。
if(prime[j] > v[i] !! prime[j] > n/i) break;
//prime[j]是合数i*prime[j]的最小质因子
v[i*prime[j]] = prime[j];
}
}
}3.欧拉函数
欧拉函数
一、定义与性质
定义：欧拉函数
性质：
当
欧拉函数是积性函数，但不是完全积性函数。
当且仅当
当
二、欧拉函数的应用
欧拉函数在数论中有着广泛的应用，特别是在密码学中的RSA算法中，欧拉函数起到了关键作用。在RSA算法中，需要选择两个大素数
三、欧拉函数前十项
由于欧拉函数的值取决于与n互质的数的个数，因此无法直接给出欧拉函数前十项的具体数值，因为每个n的值不同，φ(n)的值也会不同。但是，可以给出一些具体的例子：
虽然欧拉函数与欧拉公式、欧拉定理在名称上相似，但它们在数学上是不同的概念。欧拉公式主要在复变函数和拓扑学中使用，而欧拉定理则涉及同余的性质。因此，在讨论欧拉函数时，应注意区分这些概念。
综上所述，欧拉函数是数论中的一个重要概念，具有独特的性质和应用价值。在研究和应用欧拉函数时，应深入理解其定义和性质，并熟练掌握其计算方法。
如果只要求一个数的欧拉函数值，那么直接根据定义质因数分解的同时求就好了。这个过程可以用 Pollard Rho 算法优化。
#include <cmath>
int euler_phi(int n) {
int ans = n;
for (int i = 2; i * i <= n; i++)
if (n % i == 0) {
ans = ans / i * (i - 1);
while (n % i == 0) n /= i;
}
if (n > 1) ans = ans / n * (n - 1);
return ans;
}对任意满足
特别地，当
若
由唯一分解定理，设
对任意不全为
还可以利用欧拉筛法求出多个欧拉函数。 伪代码如下：
void eular(int n)
{
//数组phi 表示欧拉函数
int cnt = 0;
for(int i = 2;i <= n;i++)
{
if(v[i] == 0)
{
prime[++cnt] = i;phi[i] = i-1;
}
for(int j = 1;j <= cnt;j++)
{
if(prime[j]*i > n) break;
v[prime[j]*i] = 1;
if(i%prime[j] == 0)
{
phi[i*prime[j]] = phi[i]*prime[j];
break;
}
else
phi[i*prime[j]] = phi[i]*(prime[j]-1);
}
}
}4.求gcd
求最大公约数（GCD）的方法有多种，常见的包括穷举法、辗转相除法（欧几里得算法）、质因数分解法和更相减损法。
-
穷举法是最直观的方法，通过列出两个整数的所有因数，找出最大的公约数。这种方法简单易理解，但当整数较大时，计算速度较慢。
辗转相除法（欧几里得算法）通过不断将较大数除以较小数，取余数后再对两数进行同样的操作，直到余数为
0 ，此时的除数即为最大公约数。这种方法适用于大整数，计算速度快。质因数分解法是将两个整数进行质因数分解，找出公共的质因数并相乘。这种方法适用于大整数，计算速度快，但步骤较为复杂。
更相减损法是通过不断减去两个整数中的较小数，直到两数相等，此时的数为最大公约数。这种方法适用于奇数，但在整数较大时效率较低。
此外，还有一些高效的算法如Stein算法和二进制算法，这些方法利用位运算和递归来提高计算速度，特别适用于计算机实现。
#include<stdio.h>
int gcd(int m,int n){
while(m%n!=0){
int r=m%n;
m=n;
n=r;
}
return n;
}
int main(){
int m,n;
scanf("%d%d",&m,&n);
printf("%d\n",gcd(m,n));
return 0;
}递归版
int gcd(int x,int y){return(y?gcd(y,x%y):x);}扩展：
最小公倍数
5.费马小定理
费马小定理(Fermat's little theorem)是数论中的一个重要定理，在1636年提出。如果
应用 应用
注意：费马小定理只是素数判定的一个必要条件，素数一定满足费马小定理，满足费马小定理的数，却不一定是素数，例如Carmichael数（Carmichael数都是符合费马小定理的，但是他们都是合数）。
引理1：若
引理2：设
费马小定理是初等数论四大定理（威尔逊定理，欧拉定理（数论中的欧拉定理），中国剩余定理(又称孙子定理），费马小定理）之一，在初等数论中有着非常广泛和重要的应用。实际上，它是欧拉定理的一个特殊情况, 即
p3381 exmple:
#define ll long long
ll fpm(ll x, ll power, ll mod) {
x %= mod;
ll ans = 1;
for (; power; power >>= 1, (x *= x) %= mod)
if(power & 1) (ans *= x) %= mod;
return ans;
}
int main() {
ll x = fpm(a, p - 2, p); //x为a在mod p意义下的逆元
}6.扩展欧几里得
扩展欧几里得算是欧几里得算法（辗转相除法）的扩展。它不仅能计算两个整数
扩展欧几里得算法的应用领域
扩展欧几里得算法在工程和数学领域有广泛应用。它常用于求解模线性方程及方程组，特别是在需要求解贝祖等式
int exgcd(int a,int b,int &x,int &y){
int ret,tmp;
if(b==0){
x=1;y=0;return a;
}
ret=exgcd(b,a%b,x,y);
tmp=x;x=y;y=tmp-a/b*y;
return ret;
}扩展欧几里得算法求逆元
使用辗转相除法求最大公约数：从
#include <iostream>
using namespace std;
// 扩展欧几里得算法求逆元
long long exgcd(long long a, long long b, long long &x, long long &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
long long d = exgcd(b, a % b, x, y);
long long t = x;
x = y;
y = t - (a / b) * y;
return d;
}
int main() {
long long a, b, x, y;
cin >> a >> b; // 读取a和b的值
long long d = exgcd(a, b, x, y);
if (d != 1) {
cout << "无逆元" << endl;
} else {
// 输出模b的逆元
cout << (x % b + b) % b << endl;
}
return 0;
}线性求逆元
线性求逆元的方法可以通过递推公式实现，其时间复杂度为
递推公式：设
为使
公式：
设正整数
有整数解。并且在模
其中
扩展：模数不互质的情况
两个方程
设两个方程分别是
将它们转化为不定方程：
由 裴蜀定理，当
其他情况下，可以通过 扩展欧几里得算法 解出来一组可行解
则原来的两方程组成的模方程组的解为
多个方程:
用上面的方法两两合并即可。
8.杨辉三角（组合数）
杨辉三角，是二项式系数在三角形中的一种几何排列，中国南宋数学家杨辉1261年所著的《详解九章算法》一书中出现。在欧洲，帕斯卡（1623----1662）在1654年发现这一规律，所以这个表又叫做帕斯卡三角形。帕斯卡的发现比杨辉要迟393年，比贾宪迟600年。
性质：
前提：每行端点与结尾的数为1. （与上图中的n不同，这里第一行定义为n=1）
- 每个数等于它上方两数之和。
- 每行数字左右对称，由1开始逐渐变大。
- 第
n 行的数字有n 项。 - 前
n 行共(1+n)n/2 个数。 - 第
n 行的m 个数可表示为C(n-1，m-1) ，即为从n-1 个不同元素中取m-1 个元素的组合数。 - 第
n 行的第m 个数和第n-m+1 个数相等 ，为组合数性质之一。 - 每个数字等于上一行的左右两个数字之和。可用此性质写出整个杨辉三角。即第
n+1 行的第i 个数等于第n 行的第i-1 个数和第i 个数之和，这也是组合数的性质之一。即C(n+1,i)=C(n,i)+C(n,i-1) 。 -
- 将第
2n+1 行第1 个数，跟第2n+2 行第3 个数、第2n+3 行第5 个数……连成一线，这些数的和是第4n+1 个斐波那契数；将第2n 行第2 个数(n>1) ，跟第2n-1 行第4 个数、第2n-2 行第6 个数……这些数之和是第4n-2 个斐波那契数。 - 将第
n 行的数字分别乘以10^{m-1} ，其中m 为该数所在的列，再将各项相加的和为11^(n-1) 。11^2=1 \times 10^0+2 \times 10^1+1 \times 10^2=121，11^3=1 \times 10^0+3 \times 10^1+3 \times 10^2+1 \times 10^3=1331，11^4=1 \times 10^0+4 \times 10^1+6 \times 10^2+4 \times 10^3+1 \times 10^4=14641，11^5=1 \times 10^0+5 \times 10^1+10 \times 10^2+10 \times 10^3+5 \times 10^4+1×10^5=161051$。 - 第
n 行数字的和为2^{n-1} 。 - 斜线上数字的和等于其向左（从左上方到右下方的斜线）或向右拐弯（从右上方到左下方的斜线），拐角上的数字。
- 将各行数字左对齐，其右上到左下对角线数字的和等于斐波那契数列的数字。
加法 & 乘法原理
加法原理
完成一个工程可以有
乘法原理
完成一个工程需要分
排列数
从
全排列：
全排列是排列数的一个特殊情况。
组合数
从
如何理解上述公式？我们考虑
组合数也常用
因此，从
code:
递归方法
递归方法通过枚举所有可能的组合。例如，从1到5中选择3个数的组合可以通过递归实现：
#include<iostream>
using namespace std;
void dfs(int u, int sum, int state) {
if (u == k) {
// 输出当前组合
cout << "组合: ";
for (int i = 0; i < n; i++) {
if (state & (1 << i)) {
cout << i + 1 << " ";
}
}
cout << endl;
return;
}
dfs(u + 1, sum + 1, state | (1 << u)); // 选择第u个数
dfs(u + 1, sum, state); // 不选择第u个数
}
int main() {
int n = 5, k = 3; // 从5个数中选择3个数
dfs(0, 0, 0); // 调用递归函数
return 0;
}
这种方法直观易懂，但效率较低，适用于小规模数。 递推预处理方法
递推预处理方法通过计算组合数的性质进行优化。例如，组合数满足递推关系：
void init_C() {
int N = 100; // 预处理的最大下标
vector<vector<int>> c(N + 1, vector<int>(N + 1, 0));
for (int i = 0; i <= N; i++) {
c[i] = c[i][i] = 1; // C_i^0 和 C_i^i 都为1
for (int j = 1; j < i; j++) {
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % P; // P为模数，防止溢出
}
}
}扩展：Lucas定理
Lucas定理是用来求
Lucas定理：令
时间
int Lucas (ll n , ll m , int p)
{
return m == 0 ? 1 : 1ll*comb (n%p , m%p , p) * Lucas (n/p,m/p,p)%p ;
}
//comb()函数中，因为q ， r < p , 所以这部分暴力完成即可。
//C++求C(n, m) mod 10007 版本二 要求p z在100000左右
ll f[N];
void init(int p)
{ //f[n] = n!
f[0] = 1;
for (int i=1; i<=p; ++i) f[i] = f[i-1] * i % p;
}
ll pow_mod(ll a, ll x, int p)
{
ll ret = 1;
while (x)
{
if (x & 1) ret = ret * a % p;
a = a * a % p;
x >>= 1;
}
return ret;
}
ll Lucas(ll n, ll k, int p) //C (n, k) % p
{
ll ret = 1;
while (n && k)
{
ll nn = n % p, kk = k % p;
if (nn < kk) return 0; //inv (f[kk]) = f[kk] ^ (p - 2) % p
ret = ret * f[nn] * pow_mod (f[kk] * f[nn-kk] % p, p - 2, p) % p;
n /= p, k /= p;
}
return ret;
}
int main(void)
{
init (p);
printf ("%I64d\n", Lucas (n, m, p));
return 0;
}