28176 Maximum GCD

토요 라운드 끝나고 나서 힌트 받아가며 풀었던 문제

 

토요 라운드 중에 어느정도 감은 잡았다

 

10같은 경우를 예로 들면

10%10 = 0

10%9 = 1

10%8 = 2

10%7 = 3

10%6 = 4

10%5 = 0

 

최대 나올 수 있는 나머지 값이 4이다.

 3 7 10을 예로 들면 7과 10은 각각 1..3, 1..4까지 나머지를 만들 수 있으니 정답은 3이 된다.

 

이까지는 알겠는데 7 7 7 같은 경우나 2 4 8같은 경우를 어떻게 할지 몰라서 막혔다.

 

-> 결국 가장 작은 값을 가지고 최대공약수인지, 나머지로 만들 수 있는지 비교하면 된다

 

하지만 틀렸는데....

 

10 12 19의 경우 정답이 4인줄 알았는데 5여야 했다.

12 19로 5를 만들면 10 5 5여서 정답은 5가 된다.

 

그래서 확인해야 하는 게

- 자기자신(10)

- 자기 자신 외 가장 큰 약수(5)

위 경우가 아닌 경우 자기자신이 만들 수 있는 최대 나머지가 답이다

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>
#include <math.h>
#include <sstream>
#include<cassert>
#include <climits>
#include <tuple>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
#define MAXV 1e13 + 1
#define FOR(i, n) for(int i = 0; i < (n); ++i)

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int n;
i64 v[100005];

i64 gcd(i64 a, i64 b){
    if(b == 0)
        return a;
    return gcd(b, a % b);
}

bool isGcd(i64 x) {
    FOR(i, n) {
        if (gcd(x, v[i]) == x)
            continue;
        if ((v[i]-1)/2 >= x)
            continue;
        return false;
    }
    return true;
}

int main() {
    scanf("%d", &n);
    
    i64 minv = MAXV;
	FOR(i, n) {
	    scanf("%lld", &v[i]);
	    minv = min(minv, v[i]);
	}
	
	if (isGcd(minv)) cout << minv;
	else if (isGcd(minv/2)) cout << minv/2; 
	else cout << (minv-1)/2;
    
	return 0;
}