ZOJ 2657/POJ 1061 Appointment/青蛙的约会 (扩展欧几里得)

数论入门题目,讲解网上好多的,但是我感觉看完算法导论之后的理解更深刻一些,尤其是用群论来解释的东西,非常好,在此只是贴下模板什么的。。

#include<iostream>
using namespace std;
typedef long long LL;

//欧几里得算法
LL gcd(LL a,LL b) 
{
    if( b == 0 ) return a;
    else return gcd(b,a%b);
} 
//计算机中的模与数论中的不一样,需要转换 
LL geizheng(LL a,LL n)
{
    if( a < 0 ) 
        return n+a%n;
    return a%n;
}
//扩展欧几里得
LL ext_euclid(LL a,LL b,LL &x,LL &y)
{
    LL t,d;
    if( b == 0 )
    {
        x = 1;
        y = 0;
        return a;
    }
    d = ext_euclid(b,a%b,x,y);
    t = x;
    x = y;
    y = t - (a/b)*y;
    return d;
} 
void gao(LL a,LL b,LL l)
{
    LL x,y,t;
    LL d = ext_euclid(a,l,x,y);
    //cout << a << ' '<< b << ' '<< d << endl;
    if( b%d ) cout << "Pat\n";
    else
    {
        x *= b/d;
        cout << geizheng(x,l/d) << endl;
    }
}

int main(void)
{
    LL m,n,a,b,l,i,j;
    while( cin >>a>>b>>m>>n>>l )
    {
        if( m == n )
            cout<<"Pat\n";
        else if( m > n )
            gao(m-n,geizheng(b-a,l),l);
        else
            gao(n-m,geizheng(a-b,l),l);
    }
    return 0;
}

继续阅读 →