UVa 11827 Maximum GCD
题意:给你一组数,让你求任意两组数的最大公约数,找出其中最大的最大公约数。数据不大直接暴力,就是读入太坑了,不知道数据是长什么样。
上代码:
直接利用C++特性来读入:
1 #include<iostream> 2 #include<sstream> 3 #include<cstdio> 4 #include<string> 5 #include<algorithm> 6 using namespace std; 7 int gcd(int x,int y)//求两个数的公约数 8 { 9 int tmp; 10 while(y!=0) 11 { 12 tmp=x%y; 13 x=y; 14 y=tmp; 15 } 16 return x; 17 } 18 int main() 19 { 20 int n,x; 21 string s; 22 int a[105]; 23 cin>>n; 24 getchar(); 25 while(n--) 26 { 27 int ans=0,cnt=1; 28 getline(cin,s);//按行读入 29 stringstream ss(s);//字符串流 30 while(ss>>a[cnt])//遇到空格或者回车停止向a[]流入,已进行强制转换 31 { 32 cnt++; 33 } 34 cnt--; 35 for(int i=1;i<cnt;i++) 36 for(int j=i+1;j<=cnt;j++) 37 { 38 ans=max(ans,gcd(a[i],a[j]));//求最大公约数 39 } 40 printf("%d ",ans); 41 } 42 return 0; 43 }
还有一种方法,就是利用ungetc函数,在遇到空格或回车之前将已读入的数字返回到读取口和接下来读到的放一起。
代码:
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 using namespace std; 5 int gcd(int x,int y)//求两个数的公约数 6 { 7 int tmp; 8 while(y!=0) 9 { 10 tmp=x%y; 11 x=y; 12 y=tmp; 13 } 14 return x; 15 } 16 int main() 17 { 18 int n,x; 19 char c; 20 int a[105]; 21 cin>>n; 22 while(getchar()!=' '); 23 while(n--) 24 { 25 int ans=0,cnt=0; 26 while((c=getchar())!=' ') 27 { 28 if(c>='0'&&c<='9') 29 { 30 ungetc(c,stdin); 31 scanf("%d",&a[++cnt]); 32 } 33 } 34 for(int i=1;i<cnt;i++) 35 for(int j=i+1;j<=cnt;j++) 36 { 37 ans=max(ans,gcd(a[i],a[j]));//求最大公约数 38 } 39 printf("%d ",ans); 40 } 41 return 0; 42 }