Problem Solving►UVa

UVa 11827 - Maximum GCD

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址

找某一對數字其 GCD 為最大的。

Solution

用 std::stringstream 來處理輸入，接著暴力做 GCD 找最大的即可。

Code

UVa 11827
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<cstdio>
#include<iostream>
#include<string>
#include<sstream>
using namespace std;

inline int gcd(int a, int b)
{
    while (b)
    {
        int temp = a%b;
        a = b;
        b = temp;
    }

    return a;
}
int main()
{
    int n, num[100];
    string str;
    scanf("%d", &n);
    getchar();
    while (n--)
    {
        int max = 0, i = 0, temp;

        getline(cin, str);
        stringstream ss(str);
        while (ss >> temp)
            num[i++] = temp;

        for (int j = 0; j < i; j++)
            for (int k = j + 1; k < i; k++)
            {
                int g = gcd(num[j], num[k]);
                max = max < g ? g : max;
            }

        printf("%d\n", max);
    }

    return 0;
}