2011-08-03 17:54:25Morris
a158. 11827 - Maximum GCD
a158. 11827 - Maximum GCD
/**********************************************************************************/
/* Problem: a158 "11827 - Maximum GCD" from UVa ACM 11827 */
/* Language: C */
/* Result: AC (20ms, 232KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-03 17:17:09 */
/**********************************************************************************/
#include<stdio.h>
int gcd(int x, int y) {
int t;
while(x%y)
t = x, x = y, y = t % y;
return y;
}
main() {
int T, n, A[101], Ans, t, a, b;
char s[50000], g;
scanf("%d", &T);
getchar();
while(T--) {
gets(s), Ans = g = t = n= 0;
for(a = 0; s[a]; a++) {
if(s[a] <= '9' && s[a] >= '0')
t = t*10 + s[a] - '0', g = 1;
else {
if(g) A[n++] = t;
t = 0, g = 0;
}
}
if(g) A[n++] = t;
for(a = 0; a < n; a++)
for(b = a+1; b < n; b++) {
if(A[a] <= Ans || A[b] <= Ans) continue;
t = gcd(A[a], A[b]);
Ans = Ans > t ? Ans : t;
}
printf("%d\n", Ans);
}
return 0;
}
內容 ：
給你n個正整數,你需要去找他們所有之中最大的一對GCD值 (greatest common divisor)
輸入說明
：
第一行為測資有幾組資料 N (1<N<100)
接下來的N行是第N組資料
每組資料都有M個數字 (1<M<100) 讓你去找其中的最大的一對GCD值
example input:
輸出說明
：
對於每組資料請輸出最大的一對GCD值
範例輸入 ：
3 10 20 30 40 7 5 12 125 15 25
範例輸出 ：
20 1 25
提示
：
出處
：
/**********************************************************************************/
/* Problem: a158 "11827 - Maximum GCD" from UVa ACM 11827 */
/* Language: C */
/* Result: AC (20ms, 232KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-03 17:17:09 */
/**********************************************************************************/
#include<stdio.h>
int gcd(int x, int y) {
int t;
while(x%y)
t = x, x = y, y = t % y;
return y;
}
main() {
int T, n, A[101], Ans, t, a, b;
char s[50000], g;
scanf("%d", &T);
getchar();
while(T--) {
gets(s), Ans = g = t = n= 0;
for(a = 0; s[a]; a++) {
if(s[a] <= '9' && s[a] >= '0')
t = t*10 + s[a] - '0', g = 1;
else {
if(g) A[n++] = t;
t = 0, g = 0;
}
}
if(g) A[n++] = t;
for(a = 0; a < n; a++)
for(b = a+1; b < n; b++) {
if(A[a] <= Ans || A[b] <= Ans) continue;
t = gcd(A[a], A[b]);
Ans = Ans > t ? Ans : t;
}
printf("%d\n", Ans);
}
return 0;
}