[2020 APC] 추첨상 사수 대작전(Hard) 풀이

※ 확장 유클리드 알고리즘은 www.crocus.co.kr/1232 블로그의 도움을 많이 받았습니다. 감사합니다.

 

1. 추첨상 사수 대작전!(Easy) 풀이

www.acmicpc.net/problem/20410

20410번: 추첨상 사수 대작전! (Easy)

해당 문제에서 M의 범위는 크지 않습니다. 이중 포문을 사용한 브루트 포스를 통해 답을 구할 수 있습니다.

#include <iostream>
#include <queue>
using namespace std;

int main()
{
	int m, seed, x1, x2;
	int a = 0, c = 0, temp;
	cin >> m >> seed >> x1 >> x2;
	for (a = 0; a < m; a++)
	{
		for (c = 0; c < m; c++)
		{
			if ((a * seed + c) % m == x1)
			{
				if ((a * x1 + c) % m == x2)
				{
					cout << a << " " << c;
					return 0;
				}
			}
		}
	}

}

 

2. 추첨상 사수 대작전! (Normal) 풀이

www.acmicpc.net/problem/20411

20411번: 추첨상 사수 대작전! (Normal)

난이도가 올라가면서 m의 범위가 100,000으로 확장되었습니다. 안될걸 알면서도 해보는 것이 인간의 본능입니다. Easy의 코드를 다시 넣어볼까요? 

하지만 어림없지 시간초과!

여지없이 시간초과가 발생합니다.. 100,000의 2제곱을 순환해야 하는 계산은 언젠간 끝나겠지만, 알고리즘적으로 좋은 접근은 아니었던 것 같습니다. 하지만 A혹은 C를 고정하면, 10만을 순회하는 것은 컴퓨터에게는 식은 죽 먹기입니다(컴퓨터에게 식은 죽을 먹이면 안됩니다). 확장된 유클리드 알고리즘을 사용하여 모듈러 곱셈의 역원을 구하면, A를 고정할 수 있습니다.

 

[확장된 유클리드 호제법]

확장된 유클리드 알고리즘을 사용하면, 다음 식을 1로 만드는 C를 구할 수 있습니다.

A * C % M = 1 (A와 M은 알고 있음)

※이 알고리즘의 작동 원리는 www.crocus.co.kr/1232에 자세히 적혀 있습니다. 감사합니다.

 

www.acmicpc.net/problem/14565 문제를 풀어보고, 확장된 유클리드 알고리즘을 이해했는지 확인해 봅시다.

제 코드는 다음과 같습니다.

#include <iostream>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;

ll gcd(ll n, ll a)
{
	if (a == 0) return n;
	return gcd(a, n % a);
}

ll extended_euclid(ll n, ll a)
{//https://www.crocus.co.kr/1232
	vector<ll> Si = { 1,0 };
	vector<ll> Ti = { 0, 1 };
	vector<ll> Ri = { n, a };
	ll Qi = n / a ;
	ll r1, r2, temp;
	while (1)
	{
		r2 = Ri[Ri.size() - 2];
		r1 = Ri[Ri.size() - 1];
		
		temp = r2 % r1;
		Ri.push_back(temp);
		if (temp==0) return Ti[Ti.size()-1];
		Qi = r2 / r1;
		Si.push_back(Si[Si.size() - 2] - Si[Si.size() - 1] * Qi);
		Ti.push_back(Ti[Ti.size() - 2] - Ti[Ti.size() - 1] * Qi);

	}
}
int main()
{
	ll n, a;
	cin >> n >> a;

	cout << n - a << " ";
	if (gcd(n, a) != 1)
	{
		cout << -1;
		return 0;
	}

	ll ret = extended_euclid(n, a);
	while (ret < 0)
	{
		ret += n;
	}

	cout << ret;
	return 0;
}

우선 GCD를 확인하여 두 정수가 서로소인지 확인하고 곱셈 역원을 구하는 모습을 보실 수 있습니다.

 

서론이 길었습니다. 유클리드 호제법도 이해했고, 역원을 구하는 방법까지 알겠는데 이 문제에 어떻게 적용해야할지 막막하지 않나요? 저도 이 단계에서 가슴이 먹먹해지고... 침대에 드러눕기를 몇번 반복했습니다. 하지만 답은... 수학이었습니다. 그럼 답을 도출하는 과정을 천천히 따라가볼까요?

 

[식 세우기]

생각보다 어렵지 않습니다. 정의부터 하고 시작하겠습니다. 

A = B + C (mod 13)

위 식은 다음과 같은 의미를 지닙니다.

A % 13 = (B + C) % 13

문제에서 주어진 식은 다음과 같습니다.

X1 = (a × Seed + c) % m
X2 = (a × X1 + c) % m

주어진 변수를 이용해 식을 계산하면 더 직관적이나, 눈이 핑글핑글 돌아간다는 단점이 있으므로 [예제 입력1]을 직접 넣어보겠습니다.

[예제입력 1] m = 13, seed=5, x1 = 2, x2 = 9

위 식에 대입합니다.

2 = 5a + c  (mod 13)
9 = 2a + c  (mod 13)

우리는 A의 값을 구하고 싶습니다. 뺄셈을 통해 C를 없애보겠습니다.

-7 = 3a (mod 13)

여기서 두가지 의문이 발생합니다.

 

1) 음수 모듈러 연산은 어떻게 실행하지?

2) 그래서 어쩌라는거지? 

 

1번 의문부터 해결해봅시다. 

음수 모듈러 연산은 간단합니다. 양수가 나올 때 까지 M을 더해주면 됩니다. 어차피 우리는 나머지 연산을 수행중이므로, 어떤 값 N에 모듈러 연산중인 M을 몇번 더하더라도 같은 결과를 얻게 됩니다. 아래의 예가 이해되신다면, 2번 문제를 같이 해결해 봅시다.

7 % 13 = 7
(7+13) % 13 = 20 % 13 = 7
(20 + 13) % 13 =  33 % 13 = 7
따라서, (-7+13) % 13 = 6 % 13 = 6

이제 2번 의문을 해결해봅시다. 

이제 우리는 확장된 유클리드 알고리즘을 사용해야 합니다. 1번 의문을 통해 우리가 얻은 식은 다음과 같습니다.

6 = 3a (mod 13)

모듈러 연산만 없었다면, 양 변을 6으로 나누어주어 A를 구할 수 있었을 것입니다. 모듈러 연산은 다릅니다. 

우리는 (A * C)%M 을 1로 만드는 C값을 구하는 방법을 알고 있습니다.

아까 작성했던 확장된 유클리드 알고리즘 코드에 M(13) 과 A(6)를 넣어 C를 구해봅시다. C의 값은 11입니다.

 

그럼 이제 좌변을 1로 만드는 수, 11을 얻었습니다. 양변에 11을 곱합니다.

66 = 33a (mod 13)

66 % 13 = 1이므로, 다음과 같이 쓸수도 있겠습니다.

1 = 33a (mod 13)

우변을 1로 만드는 A를 구하기 위해, 확장된 유클리드 알고리즘 기계에 13과 33을 넣어봅시다. 

우리는 A = 2였음을 알 수 있습니다.

 

이제 우리는 A를 알고 있습니다. 브루트 포스를 통해 식을 만족하는 C를 찾을 수 있습니다. 코드는 다음과 같습니다.

#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <tuple>
#define ll long long
using namespace std;

ll extended_euclid(ll n, ll a)
{
	vector<ll> Si = { 1,0 };
	vector<ll> Ti = { 0, 1 };
	vector<ll> Ri = { n, a };
	ll Qi = n / a;
	ll r1, r2, temp;
	while (1)
	{
		r2 = Ri[Ri.size() - 2];
		r1 = Ri[Ri.size() - 1];

		temp = r2 % r1;
		Ri.push_back(temp);
		if (temp == 0) return Ti[Ti.size() - 1];
		Qi = r2 / r1;
		Si.push_back(Si[Si.size() - 2] - Si[Si.size() - 1] * Qi);
		Ti.push_back(Ti[Ti.size() - 2] - Ti[Ti.size() - 1] * Qi);

	}
}

int main()
{
	long m, seed, x1, x2 , minus_temp, x;
	long  a = 0, c1 = 0, c2 = 0, c = 0, temp, ltemp;
	cin >> m >> seed >> x1 >> x2;

	if (x1 == x2)
	{
		cout << 0 << " " << x1;
		return 0;
	}
	minus_temp = x1 - x2;
	while (minus_temp < 0) minus_temp += m;
	temp = extended_euclid(m, minus_temp);
	while (temp < 0)	temp += m;
	
	minus_temp = (seed - x1) * temp;
	while (minus_temp < 0) minus_temp += m;
	a = extended_euclid(m, minus_temp);
	while (a < 0) a += m;

	for (c = 0; c < m; c++)
	{
		if (x1 == ((a * seed)%m + c%m) % m)
		{
			if (x2 == ((a * x1)%m + c%m) % m) break;
		}
	}

	cout << a << " " << c;
	//cout << "\n x1: " << (a * seed + c) % m;
	//cout << "\n x2: " << (a * x1 + c) % m;
	return 0;	
}

 

3. 추첨상 사수 대작전!(Hard) 풀이

우리는 이제 A를 알고 있습니다. 이제 단순합니다. 식에 대입하여 C를 찾아봅시다.

X1 = (a × Seed + c) % m

모듈러 연산의 덧셈의 역원은 다음과 같습니다.

(A + C) % M = 0 일때, A과 M을 알고있다면, 
C = M-A

생각해보면 당연합니다. M에서 A를 나눈 나머지에 M-A를 더하면 M 그 자체가 되는 것입니다.

그럼 다시 식을 세워봅시다. 좌변을 0을 만드는 수는 m-X1이 될 것입니다.

X1 + (m-X1) = (a × Seed + c) + (m-X1)  (mod m)

좌변은 0이 되므로, 다음과 같이 쓸 수 있습니다.

0 = (a × Seed + c) + (m-X1)  (mod m)

C를 따로 빼줍니다.

0 = (a × Seed + (m-X1) ) + C  (mod m)

A = (a × Seed + (m-X1) ) 와 M = m을 알고 있습니다. 모듈러 연산 덧셈의 역 연산을 수행하여 C를 구할 수 있습니다.

C = m - (a × Seed + m-X1 )

정리합니다.

C =  -A * Seed + x1;

이제 우리는 A와 C를 구할 수 있습니다. 땡큐 유클리드! 코드는 다음과 같습니다.

#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <tuple>
#define ll long long
using namespace std;

ll extended_euclid(ll n, ll a)
{
	vector<ll> Si = { 1,0 };
	vector<ll> Ti = { 0, 1 };
	vector<ll> Ri = { n, a };
	ll Qi = n / a;
	ll r1, r2, temp;
	while (1)
	{
		r2 = Ri[Ri.size() - 2];
		r1 = Ri[Ri.size() - 1];

		temp = r2 % r1;
		Ri.push_back(temp);
		if (temp == 0) return Ti[Ti.size() - 1];
		Qi = r2 / r1;
		Si.push_back(Si[Si.size() - 2] - Si[Si.size() - 1] * Qi);
		Ti.push_back(Ti[Ti.size() - 2] - Ti[Ti.size() - 1] * Qi);

	}
}

int main()
{
	long m, seed, x1, x2, minus_temp, x;
	long  a = 0, c1 = 0, c2 = 0, c = 0, temp, ltemp;
	cin >> m >> seed >> x1 >> x2;

	if (x1 == x2)
	{
		cout << 0 << " " << x1;
		return 0;
	}
	minus_temp = x1 - x2;
	while (minus_temp < 0) minus_temp += m;
	temp = extended_euclid(m, minus_temp);
	while (temp < 0)	temp += m;

	minus_temp = (seed - x1) * temp;
	while (minus_temp < 0) minus_temp += m;
	a = extended_euclid(m, minus_temp);
	while (a < 0) a += m;

	c = -a * seed + x1;
	while (c < 0) c += m;

	cout << a << " " << c;
	//cout << "\n x1: " << (a * seed + c) % m;
	//cout << "\n x2: " << (a * x1 + c) % m;
	return 0;
}

저자 개인 블로그:  hipolarbear.tistory.com/