給定a,b,設G=gcd(a,b),于是有a=A*G,b=B*G(1<=A,B,gcd(A,B)=1)
對于a的多次加可以看成K*a(1<=k),轉(zhuǎn)化成(K*a)%b的所有結(jié)果能否表示成0..b-1中的所有數(shù),
假(K*a)%b=M,M=K*a-W*b(W為使M>0的最大整數(shù)),M=K*A*G-W*B*G M%G==0,
既結(jié)果是G的倍數(shù),如果想取得0..b-1中的所有數(shù)，
那么必須G=1才可能..
這算法牛X。。。
#include"stdio.h"
int main()
{
long m,n,k,i;
while(scanf("%ld%ld",&m,&n)!=-1)
{ printf("%10ld%10ld ",m,n);
k=1;
for(i=2;i<=(m>n?n:m);i++)
{
if(m%i==0&&n%i==0)
k=i;
}
if(k==1)
printf("Good Choice\n\n");
else
printf("Bad Choice\n\n");
}
}