ABC125 C - GCD on Blackboard(300)

C - GCD on Blackboard

概要

N項の数列Aが与えられる。この数列のうち1項を好きな数字に変えて数列全体のGCDを計算する（数字を変えなくてもよい。）。GCDの最大値を求めよ。

制約

1 ≦ N ≦ 2*10^5
1 ≦ A[i] ≦ 10^9

全体の方針

数字を変更する項を固定する。
このとき、その項を変えたときの数列全体のGCDの最大値は、その項以外の項でGCDをとったものに等しくなる。

方針①

変える項をすべて試す。普通にやるとO(N^2 log N)かかってしまうが、
左からの累積GCDと右からの累積GCDを使えば、累積和の要領でO(N log N)になる。

解答①

Submission #5169059 - AtCoder Beginner Contest 125

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int max_N = 100005;
int N;
vector<int> A(max_N, 0);
 
int gcd(int a, int b){
	if(b == 0) return a;
	return gcd(b, a % b);
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	cin >> N;
	rep(i, N) cin >> A[i];
 
	int l[N];
	l[0] = A[0];
	rep(i, N-1){
		l[i+1] = gcd(l[i], A[i+1]);
	}
 
	int r[N];
	r[N-1] = A[N-1];
	for(int i = N-2; i >= 0; i--){
		r[i] = gcd(r[i+1], A[i]);
	}
 
	int ans = r[1];
	for(int i = 1; i <= N - 2; i++){
		ans = max(ans, gcd(l[i-1], r[i+1]));
	}
 
	ans = max(ans, l[N-2]);
 
	cout << ans << endl;
}

方針②

ある2要素を固定する。その2要素のすべての約数に対し、その約数が「ある1項以外の項のGCD」となれば、その最大値が求める値となる。

イメージとしては次の通り。
全ての項のGCDはある1項の約数になっている。
ある1項以外の項のGCDとなる数は
①「A[0]以外の項のGCD」
②「A[1]以外の項のGCD」
③「A[i](i≧2)以外の項のGCD」の3パターンある。
①の場合は少なくともA[1]の約数である必要がある。
②の場合は少なくともA[0]の約数である必要がある。(A[1]の約数である必要はない）
③の場合は少なくともA[0]の約数である必要があり、かつA[1]の約数でもある必要がある。
よって、求める値はA[0]、A[1]の約数のなかにあることが分かる。（それ以外の値は調べる必要がない）

解答②

Submission #5169091 - AtCoder Beginner Contest 125

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int max_N = 100005;
 
 
int gcd(int a, int b){
	if(b == 0) return a;
	return gcd(b, a % b);
}
 
void addDivs(set<int> &st, int t){
	for(int i = 1; i * i <= t; i++){
		if(t % i == 0){
			st.insert(i);
			st.insert(t / i);
		}
	}
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int N;
	cin >> N;
 
	vector<int> A(N, 0);
	rep(i, N) cin >> A[i];
 
	set<int> st;
	addDivs(st, A[0]);
	addDivs(st, A[1]);
 
	int ans = 1;
 
	for(int x : st){
		int cnt = 1;
		bool chk = true;
		for(int i = 0; i < N; i++){
			if(A[i] % x != 0){
				if(cnt == 1){
					cnt--;
				}else{
					chk = false;
					break;
				}
			}
		}
 
		if(chk){
			ans = max(ans, x);
		}
	}
 
	cout << ans << endl;
}