欧几里得及扩展欧几里得

1.欧几里得 求最大公约数,最小公倍数

(1)递归的写法:

int gcd(int a,int b) {return b?gcd(b,a%b):a;}

(2)辗转相除法:

int gcd(int a,int b)
{
 if(a<b)    return gcd(b,a);
 int r;
 while(b) {r=a%b;a=b;b=r;}
 return a;
}

(3)stein+欧几里得 快速求解大数的最大公约数

i64 stein(i64 a,i64 b)
{ 
 if(a<b)   return stein(b,a);
 if(b==0) return a;
 if((a&1)==0&&(b&1)==0) return 2*stein(a>>1,b>>1);//a and b are even  
 if((a&1)==0) return  stein(a>>1,b);   // only a is  even    
 if((b&1)==0) return  stein(a,b>>1);   // only b is  even     
 return    stein((a+b)>>1,(a-b)>>1);   // a and b are odd
}

最小公倍数:

int lcm(int a,int b) {return a/gcd(a,b)*b;}

2.扩展欧几里得 求ax=b (mod m) ax+my=b 如果r=gcd(a,m)且b%r==0,则同余方程有解,其最小解为x*(b/r);

ax+by=c 如r=gcd(a,b),则存在x,y,使xa+yb=r;当x+=b,y-=a后仍然成立        
因为xa+yb+ab-ab=r;==>(x+b)a+(y-a)b=r

int exgcd(int a,int b,int &x,int &y)
{
 if(b==0) {x=1;y=0;return a;}
 int r=exgcd(b,a%b,y,x);
 y-=x*(a/b);
 return r;
}

扩展欧几里得算法
方程如下:
ax + by = gcd(a,b)(类似这样的方程)
现在我们假设 a > b,接下来就要有两种情况
1) 那么当b == 0的时候gcd(a,b)=a;
那么我们现在要解的这个方程就是
ax=a
==> x = 1, y = 0;
2)当b!=0的时候,我们可以设:
ax_1+by_1=gcd(a,b)
bx_2+(a \mod b)y_2=gcd(b,a%b)
又因为:gcd(a,b)=gcd(b,a%b)
由‚所以我们可以得到:==>ax1+by1=bx2+(a%b)y2
那么现在a%b又可以写成a-floor(a/b)*b [这里面floor()是向下取整的意思]
==>ax_1+by_1=bx_2+[a-floor(a/b)*b]*y_2
==>x_1*a+y_1*b=y_2*a+[x_2-floor(a/b)*y_2]*b
我们现在让系数相等也就是a和b当作未知数
==> x_1 = y_2
==> y_1 = x_2-floor(a/b)*y_2
那么我们就得到了扩展欧几里得的递归算法
方程a*x+b*y=c
有解的情况是:c mod gcd(a,b)==0
扩展欧几里得(Exgcd模板):

void Ex_gcd(int a, int b, int &x, int &y)
{
    if(b == 0)//递归出口
    {
        x = 1;
        y = 0;
        return;
    }
    int x1, y1;
    Ex_gcd(b, a%b, x1, y1);
    x = y1;
    y = x1-(a/b)*y1;
}

当然要先判断有没有解哦,有解的情况是:c mod gcd(a,b)==0
例如求解6x+2y=6,
首先判断是否有解;
然后运行上面的代码,结果是x=0,y=1;
此结果为6x+2y=gcd(6,2)的解。
所以结果为x=0*3,y=1*3;(其中3为6/gcd(6,2))

3.逆元

例如给两个数,7,20。
因为7*3%20=1,则3就是7的逆元。一个数a与它逆元的乘积对b取余等于1。
求逆元的公式就是套一个模板,假如说我们求a关于b的逆元就是解这个方程:
a*x + b*y == 1,这个方程就可以直接求了。求出的x就是a关于b的逆元。

HDU 1576:A/B
要求(A/B)%9973,但由于A很大,我们只给出n(n=A%9973)(我们给定的A必能被B整除,且gcd(B,9973) = 1)。
 InpuT
数据的第一行是一个T,表示有T组数据。
每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。
 OutpuT
对应每组数据输出(A/B)%9973。
 Sample Input
2
1000 53
87 123456789
 Sample Output
7922
6060
 
分析,我们要求的是(A/B)%9973,这个试子可以等价为( (a%9973)*_b )%9973,其中_b为B的逆元。可以看到a%9973正好就是题中所给的n。
所以题目就是求出B的逆元而已。

#include <iostream>

using namespace std;
void Ex_gcd(int a, int b, int &x, int &y)
{
    if(b == 0)//递归出口
    {
        x = 1;
        y = 0;
        return;
    }
    int x1, y1;
    Ex_gcd(b, a%b, x1, y1);
    x = y1;
    y = x1-(a/b)*y1;
}
int MOD(int &n,int &f)
{
   return (n%9973)*(f%9973)%9973;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,B;
        cin>>n>>B;
        int x,y;
        Ex_gcd(B,9973,x,y);
        if (x<0)
            x+=9973;
        int f=x;
        int result=MOD(n,f);
        cout<<result<<endl;
    }
    return 0;
}
0

Leave a Reply

Your email address will not be published.