HDU1014

求最大公约数：

欧几里得（Euclid）算法

又称辗转相除法，依据定理gcd(a,b)=gcd(b,a%b)

实现过程演示： sample：gcd(15,10)=gcd(10,5)=gcd(5,0)=5

C语言实现：

1 int Euclid_GCD(int a, int b)
2 {
3     return b?Euclid_GCD(b, a%b):a;
4 }


自己最开始想的是把可以得到的存在一个数组里，然后0-MOD-1挨个判断都在数组里则是GOOD CHOICE，但是当两数比较大时结果均出错，就改了数组大小改着改着还是改不对，于是百度发现可以直接最大公约数求。以后这种很简单的题做起来很麻烦的话尽量先多写几组实例挨个试找规律。
自己代码：

#include<iostream>
using namespace std;
int main(void){
int m,n;
while(scanf("%d%d",&m,&n)!=EOF){
printf("%10d%10d",m,n);
int a[1000],s=2;
a[0]=0,a[1]=m;
for(int i=1;i<1000;i++){
a[i+1]=(a[i]+m)%n;
if(a[i+1]==0) break;
else s++;
}

int w=0;
for(int i=0;i<n;i++)
for(int j=0;j<s;j++){
//怎么判断一个数组包含另一个数组所有数
if (i == a[j]) {
w++;
continue;
}
}
//printf("%d",w);
if(w==n) printf(" Good Choice ");
else
printf(" Bad Choice ");

}
return 0;
}

AC 代码：

#include<iostream>
using namespace std;
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
int main(void){
int s,m;
while(~scanf("%d%d",&s,&m))
{
if(gcd(s,m)==1) printf("%10d%10d Good Choice ",s,m);
else printf("%10d%10d Bad Choice ",s,m);
}
return 0;
}

无语不知道怎么改只能贴在这了