前置
模运算
定义: (a % b (amod b)) ,表示 (a) 除以 (b) 的余数。
加法: ((a+b) % p) 。
减法: ((a-b+p) % p) 。加 (p) 是为了防止负数。
乘法: ((a times b) % p) 。
除法无法直接运算,要用逆元(在下面会讲到)。
平方运算: 快速幂
模运算满足: 结合律,交换律,分配律 。
同余的定义及其性质
定义: 若 (a,b) 除以 (m) 的余数相同,则称 (a,b) 模 (m) 同余,记作 (a equiv b(mod m))。
由对于模n同余的所有整数组成的这个集合称为同余类(congruence class或residue class) 。
模 (m) 的同余类一共有 (m) 个,它们构成 (m) 的 完全剩余系 。
(1) 到 (m) 中与 (m) 互质的数代表的同余类共有 (varphi(m)) 个,它们构成了 (m) 的简化剩余系。
性质1: 满足对称性,同加性,同乘性,同幂性。
性质2: 若 (a equiv b(mod p),c mid a,c mid b),则 (a equiv b(mod dfrac{m}{gcd(m,c)})) 。
费马小定理
若 (p) 是质数,(forall a in Z,a^{p} equiv a (mod p)) 。当 (a,p) 互质时,则有 (a^{p-1} equiv 1(mod p)) 。
引理:当 (p) 是质数时,其因子只有 (1) 和 (p) 两个。因此,若两个数相乘是 (p) 的倍数,其中必然至少有一个是 (p) 的倍数。
当 (a) 不是 (p) 的倍数时,不存在 (x neq y) 且 (1 leq x,y 使得 (a times y equiv a times x(mod p)) 而 (x-y是 (p) 的倍数,与 (1 leq x,y 的限制矛盾。
进一步地,考虑 (1 sim p-1) 所有数,它们乘以 (a) 之后在模 (p) 意义下互不相同,说明仍得 (1 sim p-1) 所有数。
因此,(prod_{i=1}^{p-1}i equiv prod_{i=1}^{p-1}ai(mod p))。又因为 (prod_{i=1}^{p-1}i)显然不是 (p) 的倍数,所以费马小定理成立。
欧拉定理
若正整数 (a,n) 互质,(a^{varphi(n)} equiv 1(mod n)) 其中 (varphi(n)) 为欧拉函数。
设 (x_1,x_2 cdots x_{varphi(n)}) 是模 (n) 的简化剩余系,那 (ax_1,ax_2, cdots ax_{varphi(n)}) 也是模 (n) 的简化剩余系。
因为 (gcd(a,n)=1) ,(ax_1 dot a x_2 cdots ax_{varphi(n)} equiv x_1,x_2 cdots x_{varphi(n)} (mod n)) ,所以欧拉定理成立。
可以发现费马小定理是欧拉定理的一种特殊情况。
扩展欧拉定理
若 (a,n) 互质,(a^b equiv a^{b mod varphi(n)})
若 (a,n) 不互质,当 (b>varphi(n)) 时,(a^{b equiv varphi(n)+varphi(n)})
因为证明有些复杂,见oi wiki 。
扩展欧拉定理可以用来降幂,当幂太大时,此公式可以减小复杂度,而当 (b 幂比较小,就没有必要降幂了。
例题:P4139 上帝与集合的正确用法
线性同余方程
裴蜀定理
定义: (a,b) 是不全为零的整数,对于任意整数 (x,y) , $gcd(a,b) mid ax + by $ ,且存在整数 (x,y),使得 $ax +by = gcd(a,b) $。
逆定理: 设 (a,b) 是不全为零的整数,若 (d>0) 是 (a,b) 的公约数,且存在整数 (x,y),使得 $ ax +by = d$,则 (d = gcd(a,b)) 。
特殊地,设 (a,b) 是不全为零的整数,若存在正整数 (x,y) ,使得 $ax +by =1 $ ,则 (a,b) 互质。
当有 (n) 个数时,此定理依然成立。
例题: P4549 【模板】裴蜀定理
code
#include
using namespace std;
int n;
int gcd(int x,int y)
{
return y==0?x:gcd(y,x%y);
}
int main()
{
scanf("%d",&n);
int x,y;
cin>>x;
for(int i=2;i>y;
x=gcd(x,y);
}
cout
#include
using namespace std;
int n;
int gcd(int x,int y)
{
return y==0?x:gcd(y,x%y);
}
int main()
{
scanf("%d",&n);
int x,y;
cin>>x;
for(int i=2;i>y;
x=gcd(x,y);
}
cout
扩展欧几里得算法
上文裴蜀定理,讲述了存在整数 (x,y),使得 $ax +by = gcd(a,b) $ ,这里讲述如何求解 (x,y) 。
我们设 (d=gcd(a,b))。可以用辗转相除法法求出两个数的 $ gcd$ ,所以我们假设它的另一个解是(x2,y2),满足
]
也就是
]
又因
]
代入拆开得
]
可得一个解
]
现在发现只需要求出 (x2,y2) 而我们观看一下求 (x,y) 的式子,就是辗转相除法的式子,所以我们只需递推求一下 (x2,y2,x3,y3)等。
考虑一下递推边界,当递推到(b=0) 时,
]
可转换成
]
显然 (x=1,y in Z) 时 ,方程成立。
这样就求出了方程的一组特解,我们设为 (x_0,y_0) 。
显然不定方程 $ax +by = gcd(a,b) $ 有无穷解,所以要求通解形式。
可以知道 $ Delta(ax)+Delta(by)=0$ ,设 (Delta =lvert Delta (ax) rvert = lvert Delta (by) rvert),那 (a,b mid Delta),(lcm(a,b) mid Delta) ,所以 $ Delta x$ 是 (dfrac{lcm(a,b)}{a}=dfrac{b}{d}) 的倍数,$ Delta y$ 是 (dfrac{lcm(a,b)}{b}=dfrac{a}{d}) 的倍数。
所以通解为:
begin{cases}
x=x_0+dfrac{b}{d} times k\
y=y_0-dfrac{a}{d} times k\
end{cases}
end{aligned}
]
这里 (k in Z)。
实际做题时,会让求 (x) 的最小正整数解,设 (t= dfrac{b}{d})
]
特解的数据范围:ycx 的文章 关于 exgcd 求得特解的数值范围
线性同余方程
定义:形如 (a times xequiv c (mod b) ,a,b in Z) 的方程叫做线性同余方程。
求法:
原式转换成 :
]
这个式子和扩展欧几里得算法可以求的式子有点关联。
]
设 (d=gcd(a,b)) ,由裴蜀定理可知,方程有解当 (d mid c) 。
原式又可转成:
]
这样用扩展欧几里得算法就可以求出。
模板: P1082 [NOIP2012 提高组] 同余方程
code
#include
#define int long long
using namespace std;
int c,d,x,y;
int exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1,y=1;
return a;
}
int t=exgcd(b,a%b,y,x);
y-=(a/b)*x;
return t;
}
signed main()
{
scanf("%lld%lld",&c,&d);
exgcd(c,d,x,y);
printf("%lld",(x%d+d)%d);
return 0;
}
线性同余方程组(中国剩余定理)
begin{cases}
x equiv a_1 (mod m_1)\
x equiv a_2 (mod m_2)\
cdots \
x equiv a_n (mod m_n)\
end{cases}
end{aligned}
]
中国剩余定理(crt)
上式子中 (a in Z,m in N^*,(a,m)=1)。
求解方法:
设 (M=m_1 times m_2 times cdots m_n)。
(b_i=dfrac{M}{m_i}),(b_i^{-1}) 为 (b_i) 模 (m_i) 下的逆元。
(x= sum_{i=1}^{n} a_i times b_i times b_i^{-1})
证明:
尝试为每个同余方程设一个 $ x_i,x_i equiv a_i (mod m_i)$,可以知道 $ x_i equiv 0(mod m_j) j neq i$,记为条件一。
那 (x_i) 为 (b_i) 的倍数,如果要满足条件一 (x_i=b_itimes a_i) 即可,
那要满足上面新设的同余方程,让 (x_i times b_i^{-1}) 即可,如果要让所以 (x_i) 合成一个 (x),加起来就可以了。
扩展中国剩余定理(excrt)
上面没看懂?没关系有更好理解并适用更广的扩展中国剩余定理(excrt),它不要求模数互质。
本质就是合并方程,我们把两个方程合并成新一个方程,依次类推就可以求解方程组了。
具体的说:合并方程 (x equiv a_1 (mod m_1)) 和 (x equiv a_2 (mod m_2))。
设 $x = a_1+p times m_1 $,所以
]
即:
]
这个地方可以用 exgcd 求解。
最后合并得到:
]
根据 裴蜀定理 ,(gcd(m_1,m_2)) 不是 (a_2-a_1) 因数时,方程无解。
模板:
P1495 【模板】中国剩余定理(CRT)/ 曹冲养猪
code
#include
#define int long long
using namespace std;
int n;
int a[20],b[20],ans,M=1,t[20],m[20];
int x,y;
int exgcd(int a,int b)
{
if(b==0)
{
x=1,y=0;
return a;
}
exgcd(b,a%b);
int t=y;
y=x-a/b*y;
x=t;
}
signed main()
{
cin>>n;
for(int i=1;i>b[i]>>a[i],M*=b[i];
for(int i=1;i
P4777 【模板】扩展中国剩余定理(EXCRT)
code
#include
#define int long long
using namespace std;
const int N=1e7+10;
int n;
int m[N],X[N];
int exgcd(int a, int b,int &x,int &y)
{
if(b == 0)
{
x = 1;
y = 0;
return a;
}
int d=exgcd(b, a % b,x,y);
long long tx = x;
x = y;
y = tx - a / b * y;
return d;
}
int mul(int a,int b,int mod)
{
int res=0;
while(b)
{
if(b&1)res=(res+a)%mod;
a+=a;
a%=mod;
b>>=1;
}
return res;
}
signed main()
{
int x,y,ans=0;
scanf("%lld",&n);
for(int i=1;i>m[i]>>X[i];
int a1=X[1],m1=m[1];
for(int i=2;i
乘法逆元
定义
如果一个线性同余方程 (ax equiv 1 (mod b)) 则 (x) 称为 (a mod b) 的逆元,记作 (a^{-1})。
应用: 上文提到除法无法直接取模,而用乘法逆元就可以求出。
根据定义可知 (a times a^{-1}=1) ,那
]
求解方法
求单个数的乘法逆元
当模数 (p) 为质数时,可以用 费马小定理 求解
由定义知,(x) 为 (a) 的乘法逆元
]
再由费马小定理得:
]
所以
]
用快速幂就可以求出
code
int qpow(long long a, int b) {
int ans = 1;
a = (a % p + p) % p;
for (; b; b >>= 1) {
if (b & 1) ans = (a * ans) % p;
a = (a * a) % p;
}
return ans;
}
int main()
{
a=qpow(a,p-2);//求 a 的逆元
}
当 (p) 不为质数, (gcd(a,p)=1) 时,可以用扩展欧几里得算法求出。((p) 不为质数时也可以求)。
求乘法逆元本质上就是求线性同余方程,用求线性同余方程的方法求就可以了。
线性求 (1 cdots n) 的逆元
用递推来求逆元,当递推到 (i) 时,设 (k= lfloor dfrac{p}{i} rfloor ,j= p mod i),所以
]
由此又可以推出
]
两边同乘 (i^{-1} times j^{-1}) 得:
]
所以
]
既然是递推式,就要关注递推的起始项,当 (i=1) 时,(1) 的模任何数的逆元都是 (1)。
code
inv[1] = 1;
for (int i = 2; i
代码中 (p – p/i) 是为了防负数。
求任意 (n) 个数的逆元
要求 (a_1 cdots a_n) 的逆元。
定义两个数组 (s,sv) ,(s_i) 表示前 (i) 个数的乘积, (sv_i) 表示前 (i) 个数的逆元的乘积,那这样 (a_i) 的逆元就是 (s_{i-1} times sv_i) 。
递推边界 (s_0=1),(sv_n=s_n) 的逆元。
code
s[0] = 1;
for (int i = 1; i = 1; --i) sv[i - 1] = sv[i] * a[i] % p;
for (int i = 1; i
原根
阶
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net