Codeforces Round #838 (Div. 2) D.GCD Queries

어제 있었던 라운드의 D번을 한번 풀어 보겠다.

어제는 셋이 매우 어려웠다.

A,B,C,D모두 애드혹으로 발상이 힘들었다.

하지만 퀄리티 자체는 좋은듯... 어렵긴 해도...

 

풀이의 핵심은 절대 0이 될 수 없는 ai를 배제하자는 것에서 나온다.

a,b,c 세 수가 있다고 하자.

그리고 gcd(a,b),gcd(a,c),gcd(b,c)를 알 때, 0이 될 수 없는 수를 어떻게 찾을까?

어떤 변수 x에 대해서 gcd(0,x)=x라는 사실을 이용하자.

val[a]=gcd(a,b)+gcd(a,c)

val[b]=gcd(b,a)+gcd(b,c)

val[c]=gcd(c,a)+gcd(c,b)

라고 정의하자.

세 수 a,b,c중에 0이 존재한다면, val이 가장 큰 것이 0이된다.

그것도 strictly 하게 크다.

이 성질을 이용해서, 우선은 후보 x,y를 x=a[1],y=a[2]라고 하자.

그 후 배열을 순회하면서 저 val값들을 계산해주고

만약에, i번째 수 ai를 살펴볼 때 현재 후보 x,y와 ai중 val값이 가장 큰 것이 ai라면

x,y중에 더 val값이 작은 걸 교체해주면 된다.

 

#include<bits/stdc++.h>
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using PP = pair<ll, P>;
const ll n_ = 5e4 + 105, inf = (ll)1e9 * (ll)1e9 + 7, mod = 998244353, sqrtN = 320;
ll dy[4] = { -1,0,1,0 }, dx[4] = { 0,1,0,-1 };
ll n, m, k, tc = 1, a, b, c, d, sum, x, y, z, base, ans, q;
ll gcd(ll x, ll y) {
	if (!y)return x;
	return gcd(y, x % y);
};
ll query(ll x, ll y) {
	cout << "? " << x << ' ' << y << endl;
	ll ret;
	cin >> ret;
	return ret;
}
void solve() {
	cin >> n;

	a = 1, b = 2;
	ll val = query(a, b);
	for (int i = 3; i <= n; i++) {
		x = query(a, i);
		y = query(b, i);
		if (max(x, y) + val <= x + y) {
			if (x < y) {
				a = i;
				val = y;
			}
			else {
				b = i;
				val = x;
			}
		}
	}
	cout << "! " << a << ' ' << b << endl;
	cin >> x;
	return;
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> tc;
	while (tc--)solve();
}