高程复习 欧几里得算法和扩展欧几里得算法考试前冲刺简约版

gcd(m,n)=gcd(n,m%n)

 gcd欧几里得算法标准代码求最大公约数

#include 
 
using namespace std;
 
typedef long long LL;
LL gcd(int a,int b)
{
    if(b==0)return a;
    return gcd(b,a%b);
}
int main()
{
    LL a,b;
    cin>>a>>b;
    cout<<gcd(a,b)<
    return 0;
}

LMC  最小公倍数

 这样可以防止a*b溢出

#include 
#include 
using namespace std;
typedef long long LL;
LL gcd(LL a, LL b)
{
    if(b==0)return a;
    return gcd(b,a%b);
}
int main()
{
    LL a,b,lmc;
    while(cin>>a>>b)
    {
    cout<<gcd(a,b)<
    lmc=a/gcd(a,b)*b;
    cout<
    }
    return 0;
}

#include 
#include 
using namespace std;
typedef long long LL;
int main()
{
    LL a,b,lmc,t;
    while(cin>>a>>b)
    {
        t=__gcd(a,b);
    cout<
    lmc=a/t*b;
    cout<
    }
    return 0;
}

上面这个使用了c++给我们提供的函数，要求x,y类型一致

在有些题目中我们要求求出很多个数的最大公约数和最小公倍数。 对于这种问题，基本思想就是两两合并。例如求n个数的最大公约数，就可以这样：

扩展欧几里得算法到底在干什么?

 扩展欧几里得算法用来解决这样一个问题：给定两个非零的整数a和b，求一组整数解（x，y），使得ax+by=gcd(a,b)成立，其中gcd(a,b)表示a和b的最大公约数。

  利用欧几里得算法的过程来计算x和y。已知递归边界成立时x=1，y=0 ，想办法反推出最开始的x和y。

x1=y2                     //x=y(old)

y1=x2-(a/b)y2        //y=x(old)-a/b*y(old);

扩展欧几里得算法背下来

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

一、逆元的定义    

当 ax≡1(mod b)， x即为 a 在mod b 意义下的逆元。

    逆元的数学符号是 inv ，a 在mod b 意义下的逆元记作 inv(a,b)。注意不要写反了。        

例如5x≡1（mod 3），当x=2时满足10 ≡ 1（mod3），所以称2是5在mod 3意义下的逆元。

  (a * b) % p = (a%p * b%p) %p （对）

 (a / b) % p = (a%p / b%p) %p （错）

  在求余的过程中我们发现只有除法是不能分开运算的，而当a过大时，在计算除法过程中可能会造成比较大的精度损失，所以对于这种情况我们一般会把式子转换成那么(a / b) % p = (a * inv(b) ) % p = (a % p * inv(b) % p) % p来进行计算。这样就解决了除法不能分开计算的问题。需要注意：只有a和p互质，a才有关于p的逆元

#include 
 
using namespace std;
 
void Ex_gcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return;
    }
    Ex_gcd(b,a%b,x,y);
    {
        int t;
        t=x;
        x=y;
        y=t-(a/b)*y;
    }
}
int main()
{
    int a=5,b=7,x,y;
    Ex_gcd(a,b,x,y);
    cout<
    return 0;
}

 

 

#include 
 
using namespace std;
 
void Ex_gcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return;
    }
    Ex_gcd(b,a%b,x,y);
    int t;
    t=x;
    x=y;
    y=t-(a/b)*y;
}
int main()
{
    int a,b,x,y;
    cin>>a>>b;
    Ex_gcd(a,b,x,y);
    if(x<0)
    x=(x+b)%b;
    cout<
    return 0;
}

 注意这道题没说求逆元，求的是正的最小正整数解

因为求的逆元有可能是负的，一应要考虑求出来的x是负数的情况!

 

#include 
 
using namespace std;
typedef long long LL;
void ex_gcd(LL a,LL b,LL &x,LL &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return ;
    }
    ex_gcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-(a/b)*y;
}
int main()
{
    LL n,ans,x,y;
    ex_gcd(6,1007,x,y);
    x=(x+1007)%1007;
    while(cin>>n)
    {
        ans=(n*(n+1))%1007;
        ans=(ans*(2*n+1))%1007;
        ans=(x*ans)%1007;
        cout<
    }
    return 0;
}

实在不会就背，感觉有点难理解为什么要用逆元

 考试的时候按输入案例给分，遇到这种案例你不会就是不会了，所以一定要自己多练习