문제 설명

유리수 c = a/b가 주어질 때, c mod 19260817 값을 계산하라. 이 값은 합동 방정식 bx ≡ a (mod 19260817)을 만족하는 x로 정의된다.

입력 형식

두 줄로 구성된다.
첫째 줄: 정수 a
둘째 줄: 정수 b

출력 형식

모듈로 연산 결과를 정수로 출력. 해가 없으면 "Angry!" 출력.

예제

입력:

233
666

출력:

18595654

해결 방법

a와 b는 최대 10^10001까지 가능하므로 문자열로 입력받으며, 동시에 19260817로 모듈로 연산을 수행한다.

방법 1: 확장 유클리드 알고리즘

모듈로 역원 계산을 위해 확장 유클리드 알고리즘 활용. b의 역원이 존재하지 않으면 "Angry!" 출력.

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
using ll = long long;
constexpr ll MOD = 19260817;

ll extended_gcd(ll u, ll v, ll &x, ll &y) {
    if (v == 0) {
        x = 1;
        y = 0;
        return u;
    }
    ll x0, y0;
    ll g = extended_gcd(v, u % v, x0, y0);
    x = y0;
    y = x0 - (u / v) * y0;
    return g;
}

ll get_inverse(ll num) {
    ll x, y;
    ll g = extended_gcd(num, MOD, x, y);
    if (g != 1) return -1;
    return (x % MOD + MOD) % MOD;
}

void calculate() {
    string s1, s2;
    cin >> s1 >> s2;
    ll a_val = 0, b_val = 0;
    for (char c : s1) a_val = (a_val * 10 + (c - '0')) % MOD;
    for (char c : s2) b_val = (b_val * 10 + (c - '0')) % MOD;
    
    ll inv = get_inverse(b_val);
    if (inv == -1) cout << "Angry!" << endl;
    else cout << (a_val * inv) % MOD << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    calculate();
    return 0;
}

방법 2: 페르마 소정리

모듈로가 소수이므로 b^(MOD-2)로 역원 계산. b가 MOD의 배수이면 "Angry!" 출력.

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
using ll = long long;
constexpr ll MOD = 19260817;

ll mod_exp(ll base, ll exp) {
    ll res = 1;
    base %= MOD;
    while (exp) {
        if (exp & 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return res;
}

void calculate() {
    string s1, s2;
    cin >> s1 >> s2;
    ll a_val = 0, b_val = 0;
    for (char c : s1) a_val = (a_val * 10 + (c - '0')) % MOD;
    for (char c : s2) b_val = (b_val * 10 + (c - '0')) % MOD;
    
    if (b_val == 0) {
        cout << "Angry!" << endl;
        return;
    }
    ll inv = mod_exp(b_val, MOD - 2);
    cout << (a_val * inv) % MOD << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    calculate();
    return 0;
}

constexpr을 사용해 모듈로 상수를 컴파일 타임 상수로 정의하여 런타임 성능을 향상시킨다.