『算法-ACM 竞赛-数学-数论』欧几里得定理和拓展欧几里得定理数学–数论–欧几里得定理和拓展欧几里得定理欧几里得定理:gcd(a, b) = gcd(b, a%b) 证明：我们首先约定：m = gcd(a,b) , n = gcd(b, q) , a = bp +q。（这里的 gcd 含义跟上面一样，q 的含义跟后面式子同）1. m 是 a,b 的最大公约

『算法-ACM 竞赛-数学-数论』模板整理数论–康托展开与逆康托展开模板 数论–组合数（卢卡斯+扩展卢卡斯）模板 数论–Miller_Rabin 判断素数 数论–中国剩余定理模板 数论–逆元（拓展欧几里得）模板 数论–逆元（费马小定理）模板 数学–数论–因子和线性筛 （模板) 数学–数论–随机算法–Pollard Rho 大数分解算法（纯模板带输出） 数学–数论–快速幂–最大公约数–位运算

『算法-ACM 竞赛-数学-数论』最小公倍数+最大公约数数学中约定：GCD（a，b)为 a ,b 的最大公因数 LCM（a，b）为小公倍数 必须要知道的公式: a*b = gcd(a,b) * lcm (a,b) 先说 GCD 怎么求： 123int gcd(int a,int b){ return __gcd(a,b); //不是我闹着玩，是真有这个函数} 正经的

『算法-ACM 竞赛-数学-数论』整除分块（巨 TM 详细，学不会，你来打我）1.概念从一道例题说起$在介绍整除分块之前，我们先来看一道算数题：已知正整数n，求∑i=1n⌊ni⌋\begin{aligned}已知正整数n，求\sum_{i=1}^n \left⌊\dfrac{n}{i}\right⌋\end{aligned}$ 我们写一个表格看一看 1-20 的整除是什么样子的

『算法-ACM 竞赛-数学-数论』数论定理-欧拉定理定理：若 GCD(a,m)=1，则满足$a^{\varphi (m)} \equiv 1\ (mod \ m)$ 证明:扩展欧拉定理：$a^b\equiv\begin{cases}a^{b%\phi(p)}~~~~~~~~~~~gcd(a,p)=1\a^b~~~~~~~~~~~~~~~~~~gcd(a,p)\neq1,b<

『算法-ACM 竞赛-数学-数论』快速幂-最大公约数–位运算模板ACM 常用模板合集12345678910//位运算求解最大公约数long long gcd(long long a,long long b){ if(a<b) return gcd(b,a); if(b==0) return a; if((a&1)==0&&(b&1)==0) re

『算法-ACM 竞赛-数学-数论』快速乘法+快速幂1.快速幂（快速模幂）① 求 a^b: 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667int pow(int a, int k) {

『算法-ACM 竞赛-数学-数论』康托展开与逆康托展开模板ACM 常用模板合集123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include<bits/stdc++.h>using namespace

『算法-ACM 竞赛-数学-数论』康托展开与逆康托展开康托展开 可以理解为把一个全排列映射到一个数上面，因为全排列如果按照从小到大或者从大到小，肯定是有一个确定的序列的。 一般是从小到大的序列个数。我们就是要求出这个序列的位置。，想法很简答，就是求出前面比他小的个数就可以了。 理解为一个每位都是阶乘进位的数转化为 10 进制的数。思路如下：先准备求每一位的阶乘，然后从高位开始统计后面有多少个数比他

『算法-ACM 竞赛-数学-数论』广义欧拉降幂（模板）未使用欧拉筛：适用于较少次数计算的欧拉降幂。 123456789101112131415161718192021222324252627282930313233343536373839404142#include <bits/stdc++.h>#define ll long longusing namespace std;ll a,