数论3——不定方程
rogeryi
·
2024-01-28 09:27:58
·
个人记录
裴蜀定理
\text{二元裴蜀定理：} \text{不定方程 } A*x+B*y=C \text{ 有解的前提为 } \gcd(A,B)|C
\text{多元裴蜀定理：} \sum_{i=1}^n A_i*x_i \text{ 形成的整数集等价于 } k*\gcd_{i=1}^n A_i \text{ 形成的整数集}
bool check(int a,int b,int c){
if(!a&&!b) return c==0;
if(!a||!b) return c%(a^b)==0;
return c%gcd(a,b)==0;
}
不定方程求解
扩展欧几里得算法：求不定方程a*x+b*y=gcd(a,b)的一组解
设x1,y1满足 a*x1+b*y1=gcd(a,b)
考虑不定方程 b*x2+(a%b)*y2=gcd(a,b)
所以 a*x1+b*y1=b*x2+(a%b)*y2
代入 a%b=a-[a/b]*b
得 a*x1+b*y1=b*x2+(a-[a/b]*b)*y2
整理得 a*(x1-y2)+b*(y1-x2-[a/b]*y2)=0
则 x1=y2,y1=x2+[a/b]*y2为原方程的一组解
所以，求(x1,y1)等价于求(x2,y2)，递归求解
边界为b=0
此时 a*x+0*y=gcd(a,0)=a
则 x=1.y=0是此时方程的一组解
//求解不定方程a*x+b*y=gcd(a,b)
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,y,x);
y-=a/b*x;
return d;
}
//求解不定方程a*x+b*y=c
bool solve(int a,int b,int c,int &x,int &y){
int d=exgcd(a,b,x,y);
if(c%d) return false;
a/=d;b/=d;c/=d;
x*=c;y*=c;
return true;
}
\text{如果 } (x_0,y_0) \text{ 为方程的一组解，则所有解为 } (x_0+k*\frac{b}{\gcd(a,b)},y_0-k*\frac{a}{\gcd(a,b)})
线性同余方程
a*x \equiv b \text{ }(\bmod p) \text{等价于方程 } a*x+p*y=b
费马小定理
a^{p-1} \equiv 1 \text{ } (mod \text{ } p) \text{ ，其中p为质数且 } \gcd(a,p)=1
证明：
令 {P}=1,2,3,4……,p-1
{Q}=a,2a,3a,……,(p-1)a (mod p)
{Q'}=a,2a,3a,……,(p-1)a
(1) {Q}中没有重复的元素
反证法：
设 Qi=Qj且i>j，其中0 则 Q'i-Q'j=0 (mod p) 即 a*i-a*j=0 (mod p) 即 a*(i-j)=0 (mod p) 又 (a,p)=1 所以 i-j=0 (mod p) 又 i!=j 所以 i-j>=p,矛盾 (2) {Q}是{P}的乱序 由(1)知 {Q}中没有重复 又 {Q}有(p-1)项，每项为1-(p-1)中的整数 所以 {Q}是{1,2,……,p-1}的乱序 又 {P}={1,2,……,p-1} 所以 {Q}是{P}的乱序 (3) 结论 由(2)知 П(Qi)=П(Pi) 即 (p-1)!*(a^(p-1))=(p-1)! (mod p) 即 (p-1)!*(a^(p-1)-1)=0 (mod p) 又 ((p-1)!)%p!=0 所以 a^(p-1)=1 (mod p) 证毕 逆元 适用范围：将模意义下的除法运算转化为乘法运算 定义：inv(a)满足a*x=1(mod p) 解法1：使用线性同余方程求解 解法2：使用费马小定理/欧拉定理求解 解法3：前缀积+乘法递推 //线性同余方程求逆元 int inv(int a,int p){ int x,y,d=exgcd(a,p,x,y); return x; } //欧拉定理求逆元 int inv(int a,int p){return quick(a,get_phi(p)-1,p);} //线性求逆元 int sum[maxN],ins[maxN]; void quick_inv(int a[],int inv[],int n,int p){ sum[0]=1; for(int i=1;i<=n;i++) sum[i]=1ll*sum[i-1]*a[i]%p; ins[n]=inv(sum[n],p); for(int i=n-1;i>=1;i--) ins[i]=1ll*ins[i+1]*a[i+1]%p; for(int i=n;i>=1;i--) inv[i]=1ll*ins[i]*sum[i-1]%p; } 线性同余方程组 核心思想1：构造答案 适用范围：所有模数互质 \text{特殊解：} x_0=\sum_{i=1}^n B_i* ∏_{j \ne i} A_j*inv(A_j,A_i) \text{全部解：} x=x_0+k*∏_{i=1}^n A_i //中国剩余定理 int CRT(int a[],int b[],int n){ int x=0,A=1; for(int i=1;i<=n;i++) A*=a[i]; for(int i=1;i<=n;i++){ int now_A=A/a[i]; x=(x+slow(slow(now_A,b[i],A),inv(now_A,a[i]),A))%A; } return x; } 核心思想2：逐步合并线性同余方程 适用范围：模数任意 int exCRT(int a[],int p[],int mod[],int n){ for(int i=1;i<=n;i++){ int x,y,d=exgcd(a[i],p[i],x,y); if(mod[i]%d!=0) return -1; a[i]/=d;p[i]/=d;mod[i]/=d; a[i]=inv(a[i],p[i]);a[i]=(a[i]%p[i]+p[i])%p[i]; mod[i]=slow(mod[i],a[i],p[i]); } int P=p[1],ans=mod[1]; for(int i=2;i<=n;i++){ int x,y,d=exgcd(P,p[i],x,y); int now=mod[i]-ans; if(now%d!=0) return -1; p[i]/=d;now/=d;now=(now%p[i]+p[i])%p[i]; x=slow(x,now,p[i]);x=(x%p[i]+p[i])%p[i]; P*=p[i]; ans=(ans+slow(P/p[i],x,P))%P; } return (ans%P+P)%P; } 离散对数方程 \text{离散对数方程：} k*a^x \equiv b \text{ } (\bmod p) \text{定理：} a \equiv b \text{ } (\bmod \text{ }p) \bigcup \gcd(a,c)=1 \Leftrightarrow a* c \equiv b* c \text{ }(\bmod \text{ } p*c) 时间复杂度：O(sqrt(n)) 核心思想1： 1.分块预处理，计算小于sqrt(p)的乘方 2.枚举sqrt(p)的倍数，通过减法判定结果 3.使用Hash表维护插入+查询 适用范围：gcd(a,p)=1 int BSGS(int k,int x,int y,int p){ unordered_map int sum=sqrt(p),now=y; for(int i=0;i x=quick(x,sum,p);now=k; for(int i=1;i<=(sum+2);i++){ now=1ll*now*x%p; if(Hash.find(now)!=Hash.end()) return i*sum-Hash[now]; } return -1; } 时间复杂度：O(sqrt(n)) 核心思想2： 1.通过exgcd化简方程，使得gcd(a,p)=1 2.使用BSGS求解，将结果还原 适用范围：模数任意 int exBSGS(int k,int a,int b,int p){ a%=p;b%=p;k%=p; if(b==1||p==1) return 0; if(a==0||k==0) return (b==0)?1:-1; int d=gcd(a,p),cnt=0; while(d!=1){ if(b%d) return -1; ++cnt;b/=d;p/=d;k=(k*a/d)%p; if(k==b) return cnt; d=gcd(a,p); } int ans=BSGS(k,a,b,p); if(ans==-1) return -1; return ans+cnt; }