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

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

단계별로 풀어보기

45단계(수학 2) 3번째

 

 

 

X1과 X2에 대한 식을 연립해서 풀면 X2-X1 ≡ a(X1-seed) (mod m)이므로

a= (X2-X1)*(x1-seed)^-1이다.

이때 m은 소수이므로 페르마의 소정리를 이용하면 (x1-seed)^-1 대신 (x1-seed)^m-2 (mod m)를 구하면 된다. 거듭제곱은 분할 정복으로 빠르게 풀 수 있다.

a를 구했다면 아무 식에나 대입해서 c를 구하면 된다.

예제3처럼 seed=X1=X2인 경우가 있는데, 이때는 0의 역원을 구할 수 없으므로 예외 처리를 해줘야 한다.

 

 

 

#include <iostream>
using namespace std;

int main() {
  long m, seed, x1, x2;
  
  cin >> m >> seed >> x1 >> x2;
  
  auto power= [&](long base, long expo) -> long {
    long res= 1;
    
    while(expo){
      if(expo&1)  res= (res*base)%m;
      base= (base*base)%m;
      expo/= 2;
    }
    
    return res;
  };
  
  if(seed==x1){
    cout << "0 " << x1;
    
    return 0;
  }
  
  long a= ((x2-x1+m)*power(x1-seed+m, m-2))%m;
  a= a>0?a:a+m;
  
  long c= (x2-a*x1)%m;
  c= c>0?c:c+m;
  
  cout << a << " " << c;
  
  return 0;
}