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