[BOJ] 20412 추첨상 사수 대작전

 

/******************************************************************************

                        BOJ 페르마 소정리 20412
                        X1 = (a × Seed + c) % m 
                        X2 = (a × X1 + c) % m
                        a ? c ?
*******************************************************************************/

#include <iostream>

using namespace std;
using ll = long long;
ll m,s,x1,x2;

ll mul(ll x, ll m, ll d){
    if(m == 0) return 1;
    if(m == 1) return x;
    ll p = mul(x , m/2,d);
    if(m % 2 == 0) return (p*p)%d;
    else return ((p*p)%d * x)%d;
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>m>>s>>x1>>x2;
    ll a = ((x1 - x2)* (mul(s-x1,m-2,m)% m))% m;
    if(a < 0) a += m;
    ll c = (x1 % m - (a * s) % m) % m;
    if(c < 0) c+= m;
    cout<<a<<" "<<c;
    return 0;
}