poj1597 0ms 裴蜀定理

#include<cstdio>
#include<cstring>
using namespace std;
/*这道题其实可以转化成裴蜀定理: ax+by = 1;
    题意转化成数学知识就是：ax%y=m,m要取到0-(y-1)的所有值,其中x是step，y是mod，ax表示x的整数倍，因为seed(0)=0
    该式就等价于ax+by=m,很明显，m可以取到0，就是初值，
    然后如果m要取到0-(y-1)的所有值，那么ax+by=1就一定要成立，因为如果ax+by=1,那么只要在两边同时乘(1-m-1中任何一个数)就好了，
 */
//暴力枚举也能过，但有数学思维是关键
//培养数学思维，转化问题
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
int main()
{
    int step,mod;
    while(~scanf("%d%d",&step,&mod))
    {

        printf("%10d%10d%4c",step,mod,' ');
        puts(gcd(step,mod)==1?"Good Choice\n":"Bad Choice\n");
    }
    return 0;
}