数论入门题目，讲解网上好多的，但是我感觉看完算法导论之后的理解更深刻一些，尤其是用群论来解释的东西，非常好，在此只是贴下模板什么的。。
#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;
}