斐蜀定理
内容
斐蜀定理又叫贝祖定理,它的内容是这样的:
若$a,b\in N$,那么对于任意x,y,方程$ax+by=gcd(a,b)*k(k\in N)$一定有解,且一定有一组解使$ax+by=gcd(a,b)$
推论
a,b互素的充要条件是方程$ax+by=1$有整数解。
证明
令$d=gcd(a,b)$,则$d|a,d|b$
那么就能得到$d|(ax+by)$
于是我们设s为$ax+by$能得到的最小正整数值,则$d|s$。
令$q=a\div s$(此处为整除),$r=a\mod s$,则$a=qs+r$。
->$r=a-qs$
->$r=a-q(ax+by)$
->$r=(1-qx)a+b(-qy)$
则通过观察可以发现r也是一个关于a,b的线性组合,其中$x=(1-qx),y=(-qy)$
因为$0\leq r < s$,又因为s是a,b线性组合所能得到的最小自然数,那么r既然比s小,r只能等于0.
所以既然余数为0就说明$s|a$,同理可证明$s|b$,所以能得到$s|(ax+by)$。
于是就有$s|d$,又因为上文提到了$d|s$,所以得到$s==d$
由于s是$ax+by$所得到任意值的集合中的最小者,又因为s=d,d=gcd(a,b)所以得到
$ax+by=gcd(a,b)$
证明完毕
拓展欧几里得算法
内容
所谓拓展欧几里得算法,那一定是跟欧几里得算法有一定关系的,拓展欧几里得算法所研究的问题是,讨论如何求满足斐蜀定理的一组方程的解。
方法
下面直接给出代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
|
void exgcd(ll a,ll b,ll& inv,ll& x,ll& y) { if(b) { exgcd(b,a%b,inv,x,y); ll temp=x; x=y; y=temp-a/b*y; } else { inv=a; x=1; y=0; } }
|
证明
假设a>b:
Ⅰ.当b=0时,gcd(a,b)=a,于是方程就变成了$ax=gcd(a,b)=a$,易知x=1,那么当x=1,y=0,时就得到了方程的一组解。
Ⅱ.设两方程:
$ax_1+by_1=gcd(a,b)$
$bx_2+(a\mod b)y_x=gcd(b,a\mod b)$
有欧几里得算法得$gcd(a,b)=gcd(b,a\mod b)$ 于是得到:
$ax_1+by_1=bx_2+(a\mod b)y_2$.
其中$a\mod b=a-a\div b\times b$(此处为整除),带入原式得到:
$ax_1+by_1=bx_2+ay_2-a\div b\times y_2\times b$
通过移项得到:
$ax_1+by_1=ay_2+b(x_2-a\div b\times y_2)$
则可以得到:
xxxxxxxxxx108 1#include 2#include 3#include 4#include 5#include 6#include 7using namespace std;8typedef long long ll;9#define MAXN 1510ll t;11ll n,m;12ll k;13ll a[MAXN];14ll r[MAXN];1516//唯一分解定理将mod分解为素数17ll fj(ll n)18{19 int c=0;20 for(int i=2;i<=n;i++)21 {22 while(n%i==0)23 {24 a[c++]=i;25 n/=i;26 }27 }28 return c;29}3031//快速乘取模32ll mul(ll a,ll b,ll mod)33{34 ll res=0;35 while(b)36 {37 if(b&1)res=(res+a)%mod;38 a=(a+a)%mod;39 b>>=1;40 }41 return res;42}43//计算n!%mod44ll fact(ll n,ll mod)45{46 ll res=1;47 for (int i = 1; i <= n; ++i) {48 res=(res*i)%mod;49 }50 return res;51}52void exgcd(ll a,ll b,ll &x,ll &y,ll &d)53{54 if(!b)55 {56 d=a;57 x=1;58 y=0;59 } else{60 exgcd(b,a%b,y,x,d);61 y-=x*(a/b);62 }63}64//用exgcd计算t模mod的逆元65ll inv(ll t,ll mod)66{67 ll d,x,y;68 exgcd(t,mod,x,y,d);69 return d==1?(x%mod+mod)%mod:-1;70}71//计算C(n,m)%mod:C(n,m)%mod=(n!/[m!*(n-m)!])%mod=n!%mod*inv(m!,mod)%mod*inv((n-m)!,mod)%mod72ll comb(ll n,ll m,ll mod)73{74 if(m<0||m>n)return 0;75 return fact(n,mod)inv(fact(m,mod),mod)%modinv(fact(n-m,mod),mod)%mod;76}77//lucas定理:C(n,m)%mod=C(n/mod,m/mod)C(n%mod,m%mod)%mod78ll lucas(ll n,ll m,ll mod)79{80 return m?lucas(n/mod,m/mod,mod)comb(n%mod,m%mod,mod)%mod:1;81}8283//中国剩余定理求解C(n,m)%mod=C(n,m)%(a1a2a3…)(ai为素数)84ll china(ll n,ll *d,ll *m)85{86 ll M = 1, ret = 0;87 for(int i = 0; i < n; i ++) M *= m[i];88 for(int i = 0; i < n; i ++)89 {90 ll w = M / m[i];91 ret = (ret + mul(w * inv(w, m[i]), d[i], M)) % M;92 }93 return (ret + M) % M;94}95int main()96{97 cin>>t;98 while(t–)99 {100 cin>>n>>m>>k;101 ll num=fj(k);//分解模k102 for (int i = 0; i <num; ++i) {103 r[i]=lucas(n,m,a[i]);104 }105 cout<<china(num,r,a)<<endl;106 }107 return 0;108}C++
于是就得到了x,y的递推关系,求接的过程是递归的,从最后一个解$x=1,y=0$,就能推导到第一个式子的一个解。证毕。
参考链接
Ⅰ.EXGCD证明