写点什么

来自北京大学 NOIP 金牌选手 yxc 的常用代码模板 4——数学知识

用户头像
极客good
关注
发布于: 刚刚

[](

)7.欧几里得算法


int gcd(int a, int b)


{


return b ? gcd(b, a % b) : a;


}


求欧拉函数 —— 模板题 AcWing 873. 欧拉函数


int phi(int x)


{


int res = x;


for (int i = 2; i <= x / i; i ++ )


if (x % i == 0)


{


res = res / i * (i - 1);


while (x % i == 0) x /= i;


}


if (x > 1) res = res / x * (x - 1);


return res;


}

[](

)8.筛法求欧拉函数


int primes[N], cnt; // primes[]存储所有素数


int euler[N]; // 存储每个数的欧拉函数


bool st[N]; // st[x]存储 x 是否被筛掉


void get_eulers(int n)


{


euler[1] = 1;


for (int i = 2; i <= n; i ++ )


{


if (!st[i])


{


primes[cnt ++ ] = i;


euler[i] = i - 1;


}


for (int j = 0; primes[j] <= n / i; j ++ )


{


int t = primes[j] * i;


st[t] = true;


if (i % primes[j] == 0)


{


euler[t] = euler[i] * primes[j];


break;


}


euler[t] = euler[i] * (primes[j] - 1);


}


}


}

[](

)9.快速幂


m^k mod p,时间复杂度O(logk)


int qmi(int m, int k, int p)


{


int res = 1 % p, t = m;


while (k)


{


if (k&1) res = res * t % p;


t = t * t % p;


k >>= 1;


}


return res;


}

[](

)10.扩展欧几里得算法


// 求 x, y,使得 ax + by = gcd(a, b)


int exgcd(int a, int b, int &x, int &y)


{


【一线大厂Java面试题解析+核心总结学习笔记+最新架构讲解视频+实战项目源码讲义】
浏览器打开:qq.cn.hn/FTf 免费领取
复制代码


if (!b)


{


x = 1; y = 0;


return a;


}


int d = exgcd(b, a % b, y, x);


y -= (a/b) * x;


return d;


}

[](

)11.高斯消元


递归法求组合数


// c[a][b] 表示从 a 个苹果中选 b 个的方案数


for (int i = 0; i < N; i ++ )


for (int j = 0; j <= i; j ++ )


if (!j) c[i][j] = 1;


else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;


通过预处理逆元的方式求组合数


首先预处理出所有阶乘取模的余数fact[N],以及所有阶乘取模的逆元infact[N]


如果取模的数是质数,可以用费马小定理求逆元


int qmi(int a, int k, int p) // 快速幂模板


{


int res = 1;


while (k)


{


if (k & 1) res = (LL)res * a % p;


a = (LL)a * a % p;


k >>= 1;


}


return res;


}


// 预处理阶乘的余数和阶乘逆元的余数


fact[0] = infact[0] = 1;


for (int i = 1; i < N; i ++ )


{


fact[i] = (LL)fact[i - 1] * i % mod;


infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;


}

[](

)12.Lucas 定理


p是质数,则对于任意整数 1 <= m <= n,有:


C(n, m) = C(n % p, m % p) * C(n / p, m / p) (mod p)


int qmi(int a, int k) // 快速幂模板


{


int res = 1;


while (k)


{


if (k & 1) res = (LL)res * a % p;


a = (LL)a * a % p;


k >>= 1;


}


return res;


}


int C(int a, int b) // 通过定理求组合数 C(a, b)


{


int res = 1;


for (int i = 1, j = a; i <= b; i ++, j -- )


{


res = (LL)res * j % p;


res = (LL)res * qmi(i, p - 2) % p;


}


return res;


}


int lucas(LL a, LL b)


{


if (a < p && b < p) return C(a, b);


return (LL)C(a % p, b % p) * lucas(a / p, b / p) % p;


}

[](

)13.分解质因数法求组合数


当我们需要求出组合数的真实值,而非对某个数的余数时,分解质因数的方式比较好用:


1. 筛法求出范围内的所有质数


2. 通过C(a, b) = a! / b! / (a - b)! 这个公式求出每个质因子的次数。 n!p的次数是n / p + n / p^2 + n / p^3 + ...


3. 用高精度乘法将所有质因子相乘


int primes[N], cnt; // 存储所有质数


int sum[N]; // 存储每个质数的次数


bool st[N]; // 存储每个数是否已被筛掉


void get_primes(int n) // 线性筛法求素数


{


for (int i = 2; i <= n; i ++ )


{


if (!st[i]) primes[cnt ++ ] = i;


for (int j = 0; primes[j] <= n / i; j ++ )


{


st[primes[j] * i] = true;


if (i % primes[j] == 0) break;


}


}


}


int get(int n, int p) // 求 n!中的次数


{


int res = 0;


while (n)


{


res += n / p;


n /= p;


}


return res;


}


vector<int> mul(vector<int> a, int b) // 高精度乘低精度模板


{


vector<int> c;


int t = 0;


for (int i = 0; i < a.size(); i ++ )


{


t += a[i] * b;


c.push_back(t % 10);


t /= 10;


}


while (t)


{


c.push_back(t % 10);


t /= 10;


}


return c;


}


get_primes(a); // 预处理范围内的所有质数


for (int i = 0; i < cnt; i ++ ) // 求每个质因数的次数


{


int p = primes[i];


sum[i] = get(a, p) - get(b, p) - get(a - b, p);


}


vector<int> res;


res.push_back(1);


for (int i = 0; i < cnt; i ++ ) // 用高精度乘法将所有质因子相乘


for (int j = 0; j < sum[i]; j ++ )


res = mul(res, primes[i]);

[](

)14.卡特兰数

用户头像

极客good

关注

还未添加个人签名 2021.03.18 加入

还未添加个人简介

评论

发布
暂无评论
来自北京大学NOIP金牌选手yxc的常用代码模板4——数学知识