[백준 20412] 추첨상 사수 대작전! (Hard)

문제 링크 => https://www.acmicpc.net/problem/20412

20412번: 추첨상 사수 대작전! (Hard)

---

정수론 문제이다.

 

이 문제는 특별하게 m값이 소수로 주어지고 나머지 Seed, X1, X2 값은 0보다 크고 m 보다 작은 값으로 주어진다.

 

이때 a, c를 구하기 위해서 문제에서 주어진 식을 이용해서 a, c를 구해낼 수 있다.

 

X1 = (a * Seed + c) (mod m)

X2 = (a * X1 + c) (mod m)

위 식에서 아랫식을 윗 식을 빼주면 다음과 같은 결과를 얻는다.

 

X2 - X1 = a * (X1 - Seed) (mod m)

여기서 양변에 X1 - Seed 의 역원을 곱해주면 a를 얻는다.

 

a = (X2 - X1) (X1 - Seed)^(-1) (mod m)

c = (X1 - a * Seed) (mod m)

 

그런데 m값이 특별하게 소수로 주어졌기 때문에 우리는 Fermat Little's Theorem 을 이용하여 inverse를 간단하게 구할 수 있다.  ( (X1 - Seed)^(m-1) mod m = 1 임을 이용함 )

 

즉, (X1 - Seed)^(-1) = (X1 - Seed)^(m-2) 임을 알 수 있다.

 

그러나 특별하게 X1 - Seed 값이 0인 경우 역원으 구하지 못하는 이상한 현상이 발생한다.

 

이 문제는 다행이도 스페셜 저지 문제이기 때문에 이 경우에는 a값을 0으로 두고 c값을 X1 으로 둬도 무방하다.

 

즉, X1 = Seed 이면 무조건적으로 X1 = X2 일 수 밖에 없으므로 간단하게 a = 0, c = X1 으로 해결했다.

 

풀이 code

 

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'
#define ll long long

using namespace std;

pair<ll, pair<ll, ll>> xGCD(ll a, ll b) { // returns {g, {x, y}}, ax+by=g
	if(b==0) return { a,{1,0} }; // base case
	pair<ll, pair<ll, ll>> ret=xGCD(b, a%b);
	ll g, x, y;
	g=ret.first;
	tie(x, y)=ret.second;
	return { g,{y,x-(a/b)*y} }; 
}

ll f(ll x, ll n, ll mod) {
	if(n==0) return 1;
	if(n==1) return x % mod;
	if(n%2==0) {
		ll res=f(x, n/2, mod) % mod;
		res = res * res;
		return res % mod;
	}
	else {
		ll res=f(x, n/2, mod) % mod;
		res = (res * res) % mod;
		return (x * res) % mod;
	}
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	ll m, seed, x1, x2;
	cin>>m>>seed>>x1>>x2;

	if(x1==seed) {
		ll a=0, c=x1;
		cout<< 0 <<" "<<x1;
	}
	else {
		ll a, c;
		a = (x2 - x1) % m;
		a = a < 0 ? a + m : a;
		a = (a * f(x1-seed<0?x1-seed+m:x1-seed, m-2, m)) % m;
		c = (x2 - a * x1)%m;
		c = c < 0 ? c + m : c;
		cout<<a <<" " << c;
	}
	

	return 0;
}