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

문제 : https://www.acmicpc.net/problem/20412

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

 

문제 파악하기

추첨상 사수 대작전! 시리즈의 마지막 문제입니다. 보통 시리즈로 나오는 문제들은 난이도가 올라갈수록 탐색의 범위를 점차 줄이며, 마지막에는 수식을 사용한 O(1) 알고리즘을 요구하게 됩니다. 이 문제 역시 O(1) 알고리즘을 사용해야 문제를 해결할 수 있습니다. 이 문제에서 주로 사용하는 연산자는 바로 모듈러(%) 입니다. 따라서, 우리는 모듈러(%) 연산을 적절하게 사용하여 a의 값을 구할 수 있으며, 이를 토대로 c의 값을 바로 구할 수 있습니다.

 

문제 해결하기

우선, X1과 X2를 구하는 수식을 살펴봅시다.

 

X1 = ( a*Seed + c )%M >> a*Seed + c = t1*M + X1

X2 = (a*X1 + c)%M >> a*X1 + c = t2*M + X2

 

위의 두 식을 잘 보면 두개의 식을 빼면 2개의 변수(a, c) 중 하나를 없앨 수 있다는 걸 발견할 수 있습니다. 그럼 두 식을 한번 빼서 결과를 살펴봅시다.

 

(a*Seed + c) - (a*X1 + c) = (t1*M + X1) - (t2*M + X2)

a*(Seed - X1) = M*(t1-t2) + (X1-X2)

 

여기서 양변에 M을 나눈 나머지를 구해봅시다. ( inv: M에 대한 모듈러 연산 역원 )

 

( a*(Seed - X1) )%M = ( M*(t1-t2) + (X1-X2) )%M

(a%M) * (Seed-X1)%M = M*(t1-t2)%M + (X1-X2)%M

a%M = ( (X1-X2) * inv(Seed-X1) )%M

∴ a = ( (X1-X2) * inv(Seed-X1) )%M

 

따라서, 위의 수식을 만족하는 a를 찾기 위해서는 (X1-X2) * inv(Seed-X1) 의 값을 계산하면 됩니다. 단, a의 값은 항상 0 ≤ a < M을 만족하기에 적절하게 모듈러 연산을 사용해서 a를 구하면 됩니다. 모듈러 연산의 역원을 구하기 위해서는 확장 유클리드 호제법을 활용할 수 있습니다. 다만, 확장 유클리드 호제법을 사용할 때에는 양수 값을 계산해야 하기에 Seed와 X1의 크기를 비교해서 빼는 순서를 조정하면 원하는 결괏값을 얻을 수 있습니다.

 

소스코드

#include <stdio.h>
#include <utility>
using namespace std;
typedef long long int lint;
typedef pair<lint, lint> PAIR;
 
lint M, Seed, X1, X2;
lint a, c;
 
// ax + by = 1
// b(a/bx + y) + (a%b)x = b*prev.first + (a%b)*prev.second = 1
PAIR inv(lint a, lint b) {
    if(a == 0) return {0, 1};
    else if(b == 0) return {1, 0};
    else {
        PAIR prev = inv(b, a%b);
        lint x = (prev.second%M+M)%M;
        lint y = (prev.first - (a/b)*x);
 
        return {x, y};
    }
}
 
int main() {
    scanf("%lld %lld %lld %lld", &M, &Seed, &X1, &X2);
 
   if(Seed-X1 > 0) a = ( ((X1-X2)%M+M)%M * (inv(Seed-X1, M).first+M)%M )%M;
   else a = ( ((X2-X1)%M+M)%M * (inv(X1-Seed, M).first+M)%M )%M;
        
    c = ( (X1%M - (a*Seed)%M)%M + M)%M;
 
    printf("%lld %lld", a, c);
}

후기

모듈로 연산에 대해 생각하고 연습할 수 있는 시리즈 문제입니다. easy부터 hard까지 적절하게 단계가 배분되어 있어 모듈러 연산을 연습하거나 수업으로 활용할 사람에게 딱 적절한 시리즈 문제라고 생각합니다.