Codeforces Round #781 (Div. 2) - D

 

D. GCD Guess

Problem

https://codeforces.com/problemset/problem/1665/D

Problem - 1665D - Codeforces

Interactive problem이다.

 

 너가 맞춰야 할 양의 정수 $1 \le x \le 10^9$이 있다.

 

 하나의 질문에서 너는 $a \ne b$인 두 양의 정수를 고를 수 있다. 그 질문의 답으로 $gcd(x+a, x+b)$를 받을 것이다. $gcd(n, m)$은 n과 m의 최대공약수를 의미한다.

 

 최대 30번의 질문을 하여 숨겨진 수 x를 찾아라.

 

 

Input

 첫째 줄에는 테스트 케이스의 수를 의미하는 하나의 정수 t($1 \le t \le 1000$) 가 주어진다.

 

 너가 맞춰야 할 정수 x는 다음 조건을 만족한다: ($1 \le x \le 10^9$).

 

 

Interaction

 숨겨진 숫자 x는 interaction이 시작하기 전에 정해지며, 너의 질문에 의해 바뀌지 않는다.

 

 각각의 x를 맞추기 위해 너는 30번이 넘지 않게 다음과 같은 질문을 할 수 있다:

• "? a b" ($1 \le a, b \le 2 \cdot 10^9, a \ne b$).

 이 질문에 대하여 너는 $gcd(x + a, x + b)$를 얻을 수 있다.

 

 x를 알게 되면, 다음 형식으로 한 줄을 출력하여라.

• "! x" ($1 \le x \le 10^9$).

 이후 계속해서 다음 테스트 케이스를 풀어나가면 된다.

 

 하나의 x에 대하여 30번 초과의 질문을 하거나 잘못된 질문을 하면, 프로그램은 즉시 종료되며, Wrong Answer를 받게 된다.

 

 

Example

input	output
2 1 8 1	? 1 2 ? 12 4 ! 4 ? 2000000000 1999999999 ! 1000000000

 

Note

 첫 번째 숨겨진 수는 4이다. 질문의 답변에 대한 이유는 다음과 같다:

 "? 1 2" - gcd(4+1, 4+2) = gcd(5, 6) = 1.

 "? 12 4" - gcd(4+12, 4+4) = gcd(16, 8) = 8.

 

 두 번째 숨겨진 숫자는 $10^9$. 질문의 답변에 대한 이유는 다음과 같다:

 "? 2000000000 1999999999" - $gcd(3 \cdot 10^9, 3 \cdot 10^9 - 1) = 1$.

 

 이 질문은 오로지 interaction을 이해를 위해 만들어진 것이며, 실제로 x를 찾기에 충분하진 않다.

 

Tutorial

 당시 WA를 맞긴 했지만 결과적으로 이전 글에서 소개했던 풀이가 맞았다.

https://lys7aves.tistory.com/6

[Codeforces] Codeforces Round #781 (Div. 2)

 

 이전 풀이에서도 크게 틀린 점은 없으나 몇 가지 실수한 부분과 함께 풀이를 다시 정리해 보았다.

 

 가장 먼저 알아내야 하는 것은 a와 2a를 입력으로 주면 gcd(x, a)를 구할 수 있다는 사실이다. 이는 최대공약수의 성질 중, $a \le b$에 대하여, gcd(a, b) = gcd(a, b-a)라는 성질을 이용한 것이다. a와 2a를 입력했을 때, 과정을 살펴보면 아래와 같다.

$
gcd(x + a, x + 2a) \\
= gcd(x + a, a) \\
= gcd(x, a)
$

 이를 이용하면 우리는 x와 a의 최대공약수를 구할 수 있다. 이때, x와 a의 최대공약수가 a이면 a를 답의 후보에 올려놓을 수 있을 것이다. 여기서 많은 정보를 알아내면 좋겠지만, 아쉽게도 이 방법은 x가 a냐는 질문에만 사용할 것이다.

 

 그러나 우리에게는 30번의 질문의 기회밖에 없다. 좀 더 많은 정보를 얻어야 할 필요가 있다. 이를 위해 생각한 방법이 a+k와 2a+k를 질문으로 던지는 것이다. a+k와 2a+k를 질문으로 던졌을 때 어떤 일이 일어나는지 살펴보자.

$
gcd(x + a + k, x + 2a + k) \\
= gcd(x + a + k, a) \\
= gcd(x + k, a)
$

 x+k와 a의 최대 공약수를 구할 수 있다. 그렇다면 이 정보는 도대체 어디에 쓸 수 있는 것일까? 바로 x를 a로 나눈 나머지를 구하는데 쓸 수 있다. 무슨 말이냐? 만약 gcd(x+k, a)가 a라고 해보자. 그럼 x+k는 a의 배수가 되는 것이고, 다음 식을 만족한다.

$
x+k \equiv 0 \pmod{a} \\
x \equiv -k \pmod{a}
$

 즉, 우리는 a번의 질문(k=0~a-1)을 통해 x를 a로 나눈 나머지를 구할 수 있다.

 

 여기까지 이야기하면 떠오르는 것이 있을 것이다. 여러 a들에 대한 나머지를 알고 있을 때, x를 구하는 방법. 그렇다. 중국인의 나머지 정리이다. x를 $a_i$들로 나눈 나머지들을 알고 있을 때, 중국인의 나머지 정리를 이용하면 x를 0부터 ($a_i$들의 곱-1) 사이의 수로 한정 지을 수 있게 된다. (사실 풀이를 생각한 과정은 "최대 공약수가 아닌 나머지를 알려줬으면 좋았을 텐데.... > 나머지만 알면 중국인의 나머지 정리를 쓸 수 있을 텐데.... > 어? a+k, a+2a+k를 질문하면 나머지를 알 수 있네?"였다.)

 

 이제 필요한 방법의 소개는 다 끝났다. 이제 얼마나 효율적으로 질문하느냐만이 남아 있다. 우선 중국인의 나머지 정리를 가장 효율적으로 사용하기 위해 $a_i$를 2부터 작은 소수를 차례로 넣기로 하였다. 그렇게 할 경우 2부터 29까지의 소수의 곱이 340,510,170으로 $10^9$을 넘지 않는 최댓값이 된다. (이전 풀이에서는 21을 소수로 착각해 2~23까지 계산했다 ㅜㅜ) 그러나 29 이하의 모든 소수에 대하여 $a_i$번의 질문을 통해 나머지를 구하게 되면 시간이 많이 걸리게 된다. 그래서 생각해낸 방법은 a를 $2 \cdot 3 \cdot 5 \cdot ... \cdot 29$로 고정한 채 k를 0부터 28까지 돌리는 것이다. 그렇게 되면 29 이하의 모든 소수들에 대하여 나머지를 29번 만에 구할 수 있게 된다.

 2부터 29까지의 소수로 나눈 나머지를 알고 있다면 중국인의 나머지 정리로 숨겨진 x를 0부터 340,510,170 사이 하나의 수로 한정 지을 수 있다. 그러나 그 수를 $x'$이라고 하면 우리는 진짜 x가 $x'$인지, $340,510,170 + x'$인지 $340,510,170 \times 2 + x'$인지 알 수 없다. 바로 여기서 맨 처음 말한 a와 2a 질문을 통해 x가 a인지 알아내는 방법을 사용하는 것이다! a를 $x'$와 $340,510,170 + x'$, $340,510,170 \times 2 + x'$로 하여 각각 한 번씩 질문을 해서 가능한 가장 큰 값이 답이 된다.

 

 여기까지 생각하고 신나게 코드를 짜서 제출하자 WA가 나왔다. 바로 질문 횟수가 30번을 초과했기 때문이다 ㅜㅜ. 다시 생각해보자. 2부터 29까지의 소수로 나눈 나머지를 구하는데 29번의 질문을 했고, 마지막으로 답을 확정 짓는데 3번의 질문을 했다. 총 32번의 질문을 한 것이다. 그렇다면 2번의 질문을 줄여야 하는데 어떻게 줄일 수 있을까? 나는 이를 각 방법에서 하나씩 줄였다. 우선 나머지를 구하는 질문에서 한 번의 질문을 줄일 수 있다. 29로 나눈 나머지를 알고 싶을 때 굳이 29번의 질문을 해야 할까? 28번의 질문을 했는데 나머지를 못 찾았으면 질문하지 않은 k가 나머지일 것이다. 이를 이용해 k=0을 제외하고 질문을 하여 질문 횟수를 한번 줄였다. 답을 확정 짓는 과정에서도 비슷한 방법을 사용하였다. 우선 $x'$은 답이 될 수 있기 때문에 이를 답이라 가정한 후, $340,510,170 + x'$와 $340,510,170 \times 2 + x'$만을 질문하여 이 중 답이 된다고 하는 게 있으면 답을 이 둘 중 하나로 바꿔주는 것이다. 이렇게 하면 2번의 질문을 줄여 정확히 30번의 질문으로 답을 구할 수 있게 된다

 

 

Solution

#include <bits/stdc++.h>

#define M (2*3*5*7*11*13*17*23*29)
#define MAXP 29
#define NUMP 9
#define MAX 1000000000

using namespace std;

int p[NUMP]={2,3,5,7,11,13,17,23,29};
int p_[NUMP];
int rest[NUMP];

void solve();
int CRT();

int main()
{
	int t, i, j;
	long long x;
	
	for(i=0; i<NUMP; i++){
		x = (M / p[i]) % p[i];
		for(j=1; j<p[i]; j++){
			if((x*j)%p[i] == 1){
				p_[i] = j;
				break;
			}
		}
	}
	
	cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}

void solve()
{
	int i, j, a, b, res, x, ans;
	
	for(i=0; i<NUMP; i++) rest[i] = 0;
	
	for(i=1; i<MAXP; i++){
		a = M+i;
		b = 2*M+i;
		
		cout << "? " << a << ' ' << b << '\n';
		cin >> res;
		
		for(j=0; j<NUMP; j++){
			if(res%p[j] == 0){
				rest[j] = (M-i) % p[j];
			}
		}
	}
	
	x = CRT();
	
	ans = x;
	for(i=1; M*i + x <= MAX; i++){
		a = M*i + x;
		b = a*2;
		
		cout << "? " << a << ' ' << b << '\n';
		cin >> res;
		
		if(res % a == 0) ans = a;
	}
	
	cout << "! " << ans << '\n';
}

int CRT()
{
	int i;
	long long x=0, A;
	
	for(i=0; i<NUMP; i++){
		A = M/p[i];
		A = (A * p_[i]) % M;
		A = (A * rest[i]) % M;
		x = (x + A) % M;
	}
	
	return x;
}

 

 

마치며...

 코포를 많이 해보진 않았지만 내가 풀었던 D번 문제 중 가장 어려웠던 것 같다. 그리고 코드를 짜는데도 시간이 오래 걸렸다. 여러 이유가 있을 테지만 우선 gcd를 활용하는 문제를 많이 접해보지 못했다는 게 가장 큰 원인인 것 같고, 둘째로는 interactive 문제를 많이 안 풀어봐서 코드를 테스트하고 고치는데 시간이 많이 걸렸다.

 

 오랜만에 전형적인 알고리즘에서 벗어나 머리를 쓰는 문제였고, 최대공약수의 성질과 중국인의 나머지 정리를 알아야 풀 수 있다는 점과 질문 제한이 적당히 작은 수가 아니라 정확히 30번을 질문해야 된다는 점 등의 이유로 정말 아름다운 문제였다고 생각한다. (친구들이 전부 시험 기간만 아니었으면 추천해주고 싶을 만큼)

 

 그리고 최근 interactive 문제를 많이 접하고 있는데, 매번 코드를 테스트할 때 문제가 발생한다. 직접 두 프로그램이 상호작용하는 코드를 만들 수 있으면 좋을 텐데 아직 그 방법을 몰라 매번 두 프로그램의 출력 값을 복붙 하는데 시간을 너무 많이 잡아먹고 있다. (여기에 대해 아는 게 있다면 누군가 알려줬으면 좋겠다 언제든 환영이다)