UVA - 11827 Maximum GCD（输入技巧+GCD暴力）_maximum gcd uva

本文链接：https://blog.csdn.net/weixin_44137005/article/details/105536375

该博客介绍了如何解决UVA 11827编程题，即寻找一组整数中每对数的最大公约数。题目提供输入限制，要求对于每个测试用例，找出所有可能整数对的最大公约数。示例输入和输出展示了算法的运行情况，由于数据规模小，可以采用暴力求解GCD的方法。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

Given the N integers, you have to find the maximum GCD (greatest common divisor) of every possible
pair of these integers.
Input
The first line of input is an integer N (1 < N < 100) that determines the number of test cases.
The following N lines are the N test cases. Each test case contains M (1 < M < 100) positive
integers that you have to find the maximum of GCD.
Output
For each test case show the maximum GCD of every possible pair.
Sample Input
3
10 20 30 40
7 5 12
125 15 25
Sample Output
20
1
25

只有输入的地方有坑，因为数据很小，直接暴力求gcd。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<iostream>
#include<algorithm>
using namespace std;

#define lowbit(a) (a&(-a))
#define ll long long
const int inf=0x3f3f3f3f;
const int maxn=5e5+10;
const int minn=1e6+10;
const double PI=acos(-1.0);
#define mod 1000000007
#define eps 1e-8

int a[110];

int gcd(int a,int b)
{
	return b?gcd(b,a%b):a;
}

int main()
{
	int t;
	char c;
	scanf("%d",&t);
	getchar();
	while(t--)
	{
		int cnt=0;
		while((c=getchar())!='\n')
		{
			if(c>='0'&&c<='9')
			{
				ungetc(c,stdin);
				scanf("%d",&a[cnt++]);
			}
		}
		int maxx=0;
		for(int i=0; i<cnt-1;i++)
		{
			for(int j=i+1; j<cnt; j++)
			{
				int x=gcd(a[i],a[j]);
				maxx=max(maxx,x);
			}
		}
		printf("%d\n",maxx);
	}
	return 0;
}