『算法-ACM竞赛-数学-数论』贝祖定理（裴蜀定理）
『算法-ACM 竞赛-数学-数论』贝祖定理（裴蜀定理）数学–数论–贝祖定理（裴蜀定理）定理： 裴蜀定理（或贝祖定理，Bézout’s identity）得名于法国数学家艾蒂安·裴蜀，说明了对任何整数 a、b 和它们的最大公约数 d，关于未知数 x 和 y 的线性不定方程（称为裴蜀等式）：若 a,b 是整数,且 GCD(a,b)=d，那么对于任意的整数 x,y,ax+by 都一定是 d 的
『算法-ACM竞赛-数学-数论』莫比乌斯线性筛模板
『算法-ACM 竞赛-数学-数论』莫比乌斯线性筛模板ACM 常用模板合集12345678910111213141516171819202122232425int prime[MAXN],prime_tot;bool isprime[MAXN];int mu[MAXN];void pre_calc(int limt){ mu[1]=1; for(int i=2;i<=
『算法-ACM竞赛-数学-数论』莫比乌斯反演
『算法-ACM 竞赛-数学-数论』莫比乌斯反演一、莫比乌斯反演涉及知识 1.莫比乌斯函数 2.莫比乌斯的线性筛法 3.狄利克雷卷积 4.莫比乌斯反演详解 5.整除法分块 6.杜教筛 二、μ 莫比乌斯函数定义 $μ(n)=\begin{cases}1& \text{n=1}\(-1)^k& \text{n= P1P2P3*…*Pk(其中P是质数)}\0&
『算法-ACM竞赛-数学-数论』莫比乌斯函数
『算法-ACM 竞赛-数学-数论』莫比乌斯函数定义：默比乌斯函数或缪比乌斯函数是指以下的函数 ：$μ(n)= \left{\begin{aligned}1& \ \ \ \text{若n=1};\(-1)^k& \ \ \ 若n无平方因子数，且n=p_1*p_2….*p_k ;\0& \ \ \ 若n有平方因子数\end{aligned}\
『算法-ACM竞赛-数学-数论』组合数（卢卡斯+扩展卢卡斯）模板
『算法-ACM 竞赛-数学-数论』组合数（卢卡斯+扩展卢卡斯）模板ACM 常用模板合集12345678910111213141516#include<cstdio>const int N = 2000 + 5;const int MOD = (int)1e9 + 7;int comb[N][N];//comb[n][m]就是C(n,m)void init(){ for(
『算法-ACM竞赛-数学-数论』素数
『算法-ACM 竞赛-数学-数论』素数ACM 常用模板合集定义判断： 12345678bool isPrime (int n){ for(int i=2;i*i<=n;i++) { if(n%i==0) return false; } else return false;} 埃氏筛法 123456789101112131415int primes[
『算法-ACM竞赛-数学-数论』积性函数（初步）
『算法-ACM 竞赛-数学-数论』积性函数（初步）一、定义积性函数指对于所有互质的整数 a 和 b 有性质 f(ab)=f(a)f(b)的数论函数。二、常见的积性函数φ(n) －欧拉函数μ(n) －莫比乌斯函数，关于非平方数的质因子数目gcd(n,k) －最大公因子，当 k 固定的情况d(n) －n 的正因子数目σ(n) －n 的所有正因子之和ε(n) －定义为：若 n = 1
『算法-ACM竞赛-数学-数论』直角三角形-勾股数---奇偶数列法则 a^2+b^2=c^2
『算法-ACM 竞赛-数学-数论』直角三角形-勾股数—奇偶数列法则 a^2+b^2=c^2先说勾股数： 勾股数，又名毕氏三元数 。勾股数就是可以构成一个直角三角形三边的一组正整数。勾股定理：直角三角形两条直角边 a、b 的平方和等于斜边 c 的平方（a²+b²=c²） 勾股数规律： 首先是奇数组口诀：平方后拆成连续两个数。 其次是偶数组口诀：平方的一半再拆成差 2 的两个数。