Chokudai SpeedRun 002 J - GCD β (500)

J - GCD β

概要

整数のペア(Ai, Bi)がN個ある。各ペアから1つずつ整数を選び、選んだN個の整数の最大公約数を計算することを考える。計算されうる最大公約数の最大値を求めよ。

制約

1 ≦ N ≦ 5 * 10^4
1 ≦ Ai, Bi ≦ 10^9

方針

最初のペア(A1, B1)のうちどちらか1つはかならず選ばれるため、最小公約数はA1, B1の約数のなかにある。よってA1, B1のすべての約数dについて、それが最大公約数になるように他のペアからも整数を選ぶことが出来るかを確認する。
具体的には、他のペア(Ai, Bi)について、AiもしくはBiのどちらかがdで割り切れれば、その数を選べばよい。

解答

Submission #5717163 - Chokudai SpeedRun 002

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pll;
 
set<ll> get_Divisors(ll x){
	set<ll> st;
	for(ll i = 1; i * i <= x; i++){
		if(x % i == 0){
			st.insert(i);
			st.insert(x / i);
		}
	}
 
	return st;
}
 
ll gcd(ll a, ll b) {
    if (a < 0) a = -a;
    if (b < 0) b = -b;
    if (b == 0) return a;
    else return gcd(b, a % b);
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int n;
	cin >> n;
 
	vector<ll> a(n), b(n);
	rep(i, n) cin >> a[i] >> b[i];
 
	set<ll> aDiv = get_Divisors(a[0]);
	set<ll> bDiv = get_Divisors(b[0]);
 
	ll ans = 1;
	for(auto itr = aDiv.begin(); itr != aDiv.end(); itr++){
		ll d = *itr;
		bool ok = true;
		for(int j = 1; j < n; j++){
			if(a[j] % d != 0 && b[j] % d != 0){
				ok = false;
				break;
			}
		}
 
		if(ok){
			ans = max(ans, d);
		}
	}
 
	for(auto itr = bDiv.begin(); itr != bDiv.end(); itr++){
		ll d = *itr;
		bool ok = true;
		for(int j = 1; j < n; j++){
			if(a[j] % d != 0 && b[j] % d != 0){
				ok = false;
				break;
			}
		}
 
		if(ok){
			ans = max(ans, d);
		}
	}
 
	cout << ans << endl;
}