同余和同余方程
若(frac{a-b}{m})为整数,则称(a)和(b)模(m)同余,用(aequiv b pmod{m})表示.
同余方程,即同余式中含有未知数,一般来说都有多组解.
扩展欧几里得
扩展欧几里得算法用于求解形如(ax+by=c)的方程.
裴蜀定理
若(a),(b)是整数,且(gcd(a,b)=d),那么对于任意的整数(x),(y),(ax+by)都一定是(d)的倍数,一定存在整数(x),(y),使(ax+by=d)成立.
特解
分为3种情况求解.
情况1 (c=gcd(a,b))
在辗转相除法中,通过回溯求出方程的一组特解.
具体操作:
- 当(b=0)时,(x=1),(y=0).
- 否则(x=y),(y=x-frac{a}{b}*y).
证明:在进行操作2时,(a)和(b)是分别由下一步的(b)和(a\%b)回溯而来.设(k=lfloor{frac{a}{b}} floor)(此证明中(a,b)均是这一步的而非下一步的),下一步(x)和(y)的值分别为(x')和(y').
如果我们令(y=x'),则有(egin{equation} left{ egin{aligned} overset{}ax+by=gcd(a,b) \ by'+(a\%b)*x=gcd(a,b) \ end{aligned} ight. end{equation})
( herefore kbx=b*(y'-y))
( herefore kx=y'-y)
( herefore y=y'-kx=y'-lfloor{frac{a}{b}} floor*x)
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 r=exgcd(b,a%b,x,y);
long long t=y;
y=x-(a/b)*y;
x=t;
return r;
}
情况2 (c=k*gcd(a,b))((k)为整数)
此时,把第一种情况((c=gcd(a,b)))的解(x)和(y)分别乘以(k),得到方程的解.
情况3 (gcd(a,b)
mid c)
根据裴蜀定理,原方程无整数解.
通解
假设特解为(x_0),(y_0).
则通解为(x=x_0+k*frac{b}{gcd(a,b)}),(y=y_0-k*frac{a}{gcd(a,b)})
乘法逆元
当(amequiv 1pmod{p})时,称(m)是(a)模(p)的乘法逆元.
余数的四个性质是可加性,可减性,可乘性可乘方性,但余数不能直接除.
在求(frac{a}{b}\%m)时,我们需要借助乘法逆元.
与倒数类似,设(k)是(b)的乘法逆元,则(frac{a}{b}\%m=a*k\%m).
扩展欧几里得求乘法逆元
(amequiv 1pmod{p})
( herefore am+pq=1)
如果(gcd(a,p)=1),就可以用扩展欧几里得来求乘法逆元.
long long inv(long long a,long long p) {
long long x,y;
exgcd(a,p,x,y);
while(x<0) x+=p;
return x%p;
}
费马小定理求乘法逆元
费马小定理:对于质数(p),(a^{p-1}equiv 1pmod {p})
( herefore a*a^{p-2}equiv 1pmod {p})
( herefore)当(p)是质数时,(a^{p-2})是(a)的乘法逆元.
费马小定理求乘法逆元涉及到快速幂.
long long poww(long long a,long long b,long long k) { //快速幂
if(b==1) return a%k;
long long p=1;
p=poww(a,b/2,k);
p=p*p%k;
if(b%2) p=p*a%k;
return p;
}
long long inv(long long a,long long p) {
long long t=poww(a,p-2,p);
while(t<0) t+=p;
return t;
}
中国剩余定理
中国剩余定理由儿子孙子提出.
这个定理用于求解形如(egin{equation}
left{
egin{aligned}
overset{}x &equiv y_1pmod{m_1} \
x &equiv y_2pmod{m_2} \
&{ vdots } \
x &equiv y_npmod{m_n}
end{aligned}
ight.
end{equation})的同余方程组.
求解这样的方程组,需要找出(n)个数(p_1,p_2,)...(,p_n).
对于每个(p_i) , (p_iequiv y_ipmod{m_i}),(p_iequiv 0pmod{m_j(j
ot = i)}).
最后将全部(p_i)加起来,就是方程的一个解.显然,两个相邻解的差为(lcm(m_1,m_2,)...(,m_n)).
将问题进一步简化,对于每个(p_i) , (p_iequiv 1pmod{m_i}),(p_iequiv 0pmod{m_j(j
ot = i)}).
最后计算全部(p_i*y_i)的和.
(ecause p_iequiv 0pmod{m_j(j
ot = i)})
( herefore p_iequiv 0pmod{lcm(m_1,m_2,...,m_i-1,m_i+1,...,m_n)})
设(k_i=lcm(m_1,m_2,...,m_i-1,m_i+1,...,m_n)),(p_i=l*k_i).
(l*k_iequiv 1pmod{m_i})
设(l*k_i=-s*m_i+1).
(l*k_i+s*m_i=1)
此时就可以用乘法逆元求解.
但如果有任意(i,j(1le i,jle n))使(gcd(m_i,m_j)
ot =1),扩展欧几里得就会无解,所以必须满足对于任意(i,j(1le i,jle n)),(gcd(m_i,m_j)=1).
long long crt() {
long long lcm=1,ans=0;
for(long long i=1;i<=n;i++) lcm*=x[i];
for(long long i=1;i<=n;i++) {
long long mi=lcm/x[i];
long long ni,y;
exgcd(mi,x[i],ni,y);
ans+=(mi*ni%lcm)*y[i]%lcm;
ans%=lcm;
}
while(ans<0) ans+=lcm;
return ans;
}
扩展中国剩余定理
扩展中国剩余定理用于解决上文提到过得不互质的同余方程组.它实际上就是同余方程的合并.
有如下同余方程组
(egin{equation}
left{
egin{aligned}
overset{}x &equiv y_1pmod{m_1} \
x &equiv y_2pmod{m_2}
end{aligned}
ight.
end{equation})
令(egin{equation}
left{
egin{aligned}
overset{}x &=y_1+k_1*m_1 \
x &=y_2-k_2*m_2
end{aligned}
ight.
end{equation})
( herefore y_1+k_1*m_1=y_2-k_2*m_2)
( herefore k_1*m_1+k_2*m_2=y_2-y_1)
由裴蜀定理知,当((y_2-y_1)
mid gcd(m_1,m_2))时原方程无解.
否则就可以用扩展欧几里得求出(k_1,k_2)的值.
最后将解转化为(xequiv y_1+k_1*m_1pmod{lcm(m_1,m_2)}).
如果有多于2个同余方程,就用这种方法继续合并方程.
long long excrt(){
long long m=x[1],b=y[1],t,g,x1,y1;
for(int i=2;i<=n;i++){
g=exgcd(m,x[i],x1,y1);
if((y[i]-b)%g) return -1;
x1*=(y[i]-b)/g;
t=x[i]/g;
x1=(x1%t+t)%t;
b=m*x1+b;
m=m/g*x[i];
}
while(b<0) b+=m;
return b%m;
}
BSGS
BSGS算法的名字很形象,全称是Bady Step Giant Step(大步小步),它用于求解形如(a^xequiv bpmod{m})的高次同余方程.
根据费马小定理,如果用暴力求解这种方程,那么最坏情况下时间复杂度为(O(m)).
在(m)比较大时,就必须用BSGS算法.
设(x=k_1*lceil{sqrt{m}}
ceil-k_2),即(a^{k_1*lceil{sqrt{m}}
ceil-k_2}equiv bpmod{m})
( herefore a^{k_1*lceil{sqrt{m}}
ceil}equiv b*a^{k_2}pmod{m})
我们将全部(b*a^{k_2})的值都存入哈希表(或是map或vector)中,再枚举全部(a^{k_1*lceil{sqrt{m}}
ceil}),寻找有没有(b*a^{k_2})与之匹配.
时间复杂度为(O(sqrt{m})).
此处用map实现哈希表.
long long bsgs(long long a,long long b,long long p) {
if(a==0&&b!=0) return -1;
if(b==1) return 0;
int m=ceil(sqrt(p)),k;
long long num1=1,num2=1;
map <long long, long long> _HASH;
_HASH.clear();
for(int i=1; i<=m; i++,num2=num2*a%p) _HASH[num2*b%p]=i-1;
for(int i=1; i<=m+1; i++) {
num1=num1*num2%p;
if(_HASH.count(num1)) return i*m-_HASH[num1];
}
return -1;
}
BSGS必须保证(gcd(a,m)=1).
扩展BSGS
扩展BSGS基于BSGS,它加了一些前期处理使(gcd(a,m)
ot=1)时也能求解.
设(k_1=gcd(a,m)),若(k_1
mid b)则原方程无解.
否则(a^{x-1}*frac{a}{k_1}equiv frac{b}{k_1}pmod{frac{m}{k_1}})
如果(gcd(a,frac{m}{k_1})
ot =1),就继续重复这一过程.
最终将方程化为(a^{k-t}*frac{a^t}{k_1k_2{cdots}k_t}equiv frac{b}{k_1k_2{cdots}k_t}pmod{frac{m}{k_1k_2{cdots}k_t}}).
设(M=k_1k_2{cdots}k_t) , (a^{k-t}*frac{a^t}{M}equiv frac{b}{M}pmod{frac{m}{M}})
(ecause gcd(a,frac{m}{M})=1)
( herefore gcd(frac{a^t}{M},frac{m}{M})=1)
( herefore)可以通过计算(frac{a^t}{M})的逆元来将(frac{a^t}{M})移到右式.
设(frac{a^t}{M})的逆元为(T),则(a^{k-t}equiv frac{b}{M}*Tpmod{frac{m}{M}}).
此时可直接用BSGS求解.
但有可能出现方程的解小于(t)的情况,所以需先枚举(a^i(0le ile t)equiv bpmod{m})的情况.
long long exbsgs(long long a,long long b,long long p) {
if(a==0&&b!=0) return -1;
if(b==1) return 0;
long long ki,t=0,M=1,s=1;
while((ki=gcd(a,p))!=1) {
if(b%ki!=0) return -1;
t++;
b/=ki,p/=ki;
M=M*(a/ki)%p;
if(M==b) return t;
}
long long m=ceil(sqrt(p)),k,num1=1,num2=1;
b=b*inv(M,p)%p;
map <long long, long long> _HASH;
_HASH.clear();
for(int i=1; i<=m; i++,num2=num2*a%p) _HASH[num2*b%p]=i-1;
for(int i=1; i<=m+1; i++) {
num1=num1*num2%p;
if(_HASH.count(num1)) return i*m-_HASH[num1]+t;
}
return -1;
}