ユークリッド、拡張ユークリッド関連

ユークリッド(gcd)
ユークリッドアルゴリズムは転がり相除去法によりx,yの最小公約数を求める

 
/*    （   ）：      ，        */
int gcd(int n, int m)
{
    while(m>0)//     
    {
        int c = n % m;
        n = m;
        m = c;
    }
    return n;//          
}

拡張ユークリッド
拡張ユークリッドアルゴリズムはユークリッドアルゴリズム(転がり相除算とも呼ばれる)の拡張である.このアルゴリズムは、a、bの2つの整数の最大公約数を計算することに加えて、整数x、y(そのうちの1つは負の数である可能性が高い)を見つけることができる.通常、最大公因子について述べると、ax+by=gcd(a,b)となる整数xとyが必ず存在するという非常に基本的な事実に言及する.2つの数a,bがあり、それらを転がす相除法を行い、それらの最大公約数を得ることができる-これはよく知られている.そして,転がり相除去法で生じた式を収集し,逆戻りしてax+by=gcd(a,b)の整数解を得ることができる.

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

ユークリッドを拡張することによって逆元を求める
 
(A*X)%MOD=1;kは確かに存在する
A*X=k*MOD+1;
移項可得:A*X-k*MOD=1;
だから、AとMODが互いに素を交わす時、書くことができます
A*X-k*MOD=gcd(A,MOD);
Aをa,MODをb,Xをx,−kをyとすると,上式は次のようになる.
ax+by=gcd(a,b);
これで拡張ユークリッドアルゴリズムでxを求めることができます.つまり、私たちが探している逆元です.

int mod_reverse(int a,int n)//ax=1(mod n)  a   x 
{
    int d,x,y;
    d=ex_gcd(a,n,x,y);
    if(d==1)
        return (x%n+n)%n;
    else
        return -1;
}

 
ax=c(mod b)(すなわちax+by=c(同上逆元の変化方式))のxの最小整数解を解く

int cal(int a,int b,int c)
{
    int x,y;
    int gcd=(a,b,x,y);
    if(c%gcd!=0)
        return -1;//     
    //  ax0+by0=gcd(a,b)                                    
    //    c/gcd(a,b)    
    // (a*c/gcd(a,b))*x0+(b*c/gcd(a,b))*y0=c;
    //   x1=c/gcd(a,b)*x0  y1=c/gcd(a,b)*y0;
    //     ax1+by1=c                                     
    //              x1=x0*c/gcd(a,b)     y1=y0*c/gcd(a,b)  
    x*=c/gcd; //               2      
    //             
    // b'=b/gcd(a,b);
    b/=gcd;   
    if(b<0)//    0      
        b=-b;
    //   x  +- kb'         
    // x=kb'+r
    //             r
    //         
    int ans=x%b; 
    //    r       
    if(ans<=0)
        ans+=b;
    return ans;
}