求最大公约数
原理:gcd(a,b)=gcd(b,a mod b)
辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的:
⒈ 若 r 是 a ÷ b 的余数,且r不为0, 则
gcd(a,b) = gcd(b,r)
⒉ a 和其倍数之最大公因子为 a。
另一种写法是:
⒈ 令r为a/b所得余数(0≤r<b)
若 r= 0,算法结束;b 即为答案。
⒉ 互换:置 a←b,b←r,并返回第一步。
欧几里德算法的C语言实现:
int gcd(int a,int b)
{
if(a<b){int temp;temp=a;a=b;b=temp;}
if(b==0)return a;
while(a%b){int r=a%b;a=b;b=r;}
return b;
}
递归写法:
int gcd(int a,int b)
{
if(a<b){int temp;temp=a;a=b;b=temp;}
if(b==0)return a;
return gcd(b,a%b);
}
最小公倍数 = a*b/最大公约数 注意超过范围32位
用a*(b/最大公约数)就不会超过32位了 而且有时需用到long long
扩展欧几里得算法
求ax+by=gcd(a,b)(这里a和b都是正整数所以解释了后面带入的为什么是m,n)
int extgcd(int a,int b,int &x,int &y)
{
int d=a;
if(b!=0){
d=extgcd(b,a%b,y,x);
y=y-(a/b)*x;
}
else{
x=1;y=0;
}
return d;
}
int main()
{
int x,y;
extgcd(4,11,x,y);
printf("%d %d\n",x,y);
return 0;
}
扩展欧几里得算法的应用
(1)求解不定方程
用扩展欧几里得算法解不定方程ax+by=c;
这个应该比较好理解了,两个可以同乘以k.
(2)乘法逆元
给出2个数M和N(M < N),且M与N互质,找出一个数K满足0 < K < N且K * M % N = 1,如果有多个满足条件的,输出最小的。
思路:K M % N = 1等价于 KM=NX+1 即 KM+N*(-X)=1
根据扩展欧几里德算法,求出K和(-X);
而K是应为正整数,即需要若K为负整数,则需要将之化正,即与负数取模同理,将K加上N,直至K>0为止,所得的数即为最小的乘法逆元;
若K为正整数,则直接输出即可。
int extgcd(int a,int b,int &x,int &y)
{
int d=a;
if(b!=0){
d=extgcd(b,a%b,y,x);
y=y-(a/b)*x;
}
else{
x=1;y=0;
}
return d;
}
int main()
{
int m,n,x,y;
scanf("%d%d",&m,&n);
extgcd(m,n,x,y);
printf("%d\n",(x%n+n)%n); //要使K最小,而且考虑K为负数的情况
return 0;
}
例如:4关于1模7的乘法逆元为多少?
4X≡1 mod 7
这个方程等价于求一个X和K,满足4X=7K+1,其中X和K都是整数。
若ax≡1 mod f, 则称a关于模f的乘法逆元为x。也可表示为ax≡1(mod f)。
为什么要有乘法逆元呢?
当我们要求(a/b) mod p的值,且a很大,无法直接求得a/b的值时,我们就要用到乘法逆元。
我们可以通过求b关于p的乘法逆元k,将a乘上k再模p,即(a*k) mod p。其结果与(a/b) mod p等价。
用乘法逆元求组合数:
#define MOD 1000000007
long long extgcd(long long a,long long b,long long &x,long long &y)
{
long long d=a;
if(b!=0){
d=extgcd(b,a%b,y,x);
y=y-(a/b)*x;
}
else{
x=1;y=0;
}
return d;
}
long long hx(long long a,long long b)
{
long long x,y;
extgcd(a,b,x,y);
return (x%b+b)%b;
}
long long comb(long long n,long long m)
{
long long fz=1,fm=1;
int i;
for(i=n;i>=m+1;i--)
fz=(fz*i)%MOD;
for(i=n-m;i>=2;i--)
fm=(fm*i)%MOD;
return (fz*hx(fm,MOD))%MOD;
}
int main()
{
long long m,n;
scanf("%lld%lld",&m,&n);
printf("%lld\n",comb(m,n));
return 0;
}
求解二元一次方程:
void extgcd(long long a,long long b,long long &d,long long &x,long long &y)
{
if(!b){d=a;x=1;y=0;}
else{extgcd(b,a%b,d,y,x);y-=x*(a/b);}
}
int main()
{
long long x,y,m,n,l,d,a,b,c;
scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l);
a=m-n;b=l;c=y-x;
extgcd(a,b,d,x,y);
if(c%d)printf("Impossible\n");
else
{
x=x*(c/d);//c可以整除d
b=b/d;
if(b<0)b=-b;
printf("%lld\n",(x%b+b)%b);
}
return 0;
}
求模线性方程组
以POJ 2891为例:
题意:给你k对a和r是否存在一个正整数x使每队a和r都满足:x mod a=r,求最小正解x或无解。
思路:
若模数两两互质,我们可以用中国剩余定理来解。
这里我们先考虑两个方程:
我们可以写成:
相减得:
这就可以用扩展欧几里得解方程求出解:
设a, b, c为任意整数。若方程ax+by=c的一组整数解为(x0,y0),则它的任意整数解都可以写成(x0+kb’,y0-ka’),其中a’=a/gcd(a,b),b’=b/gcd(a,b),k取任意整数。
设a, b, c为任意整数,g=gcd(a,b),方程ax+by=g的一组解是(x0,y0),则当c是g的倍数时ax+by=c的一组解是(x0c/g,y0c/g);当c不是g的倍数时无整数解。
若gcd(a,b)/|m那么方程就无解,直接输出-1。
否则我们可以解出上式的y1。回带得到一个特解x0=r1−y1a1。
通解可以写成x=x0+k∗lcm(a1,a2)也就是x≡x0(mod lcm(a1,a2))。
这样我们就将两个方程合并为了一个。重复进行以上操作,我们最终能将n个方程全部合并,再用扩展欧几德得解出来就好了。
long long a[100010],r[100010];
long long extgcd(long long a,long long b,long long &x,long long &y)
{
long long d=a;
if(b!=0){
d=extgcd(b,a%b,y,x);
y=y-(a/b)*x;
}
else{
x=1;y=0;
}
return d;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i<n;i++)
scanf("%lld%lld",&a[i],&r[i]);
long long rr=r[0];
long long aa=a[0];
long long x,y,d;
int sign=0;
for(int i=1;i<n&&sign==0;i++)
{
d=extgcd(aa,a[i],x,y);
//printf("%lld\n",x);
if((rr-r[i])%d!=0)sign++;
x=(rr-r[i])/d*x%a[i];//注意要模a[i]
//printf("%lld\n",x);
rr=rr-x*aa;
aa=aa/d*a[i];//不能写成aa*a[i]/d会溢出
rr=rr%aa;//这个rr可能很大,所以要模掉,模掉也没有影响
}
if(sign)printf("-1\n");
else printf("%lld\n",(rr%aa+aa)%aa);
}
return 0;
}
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!