문제 풀이 위의 식을 구하는 것이 문제의 답이다. 페르마의 소정리에 의해 밑의 식이 성립한다. 즉 b^(-1) (mod X)는 b^(X - 2)이므로, 이 b^(X - 2)만 구하면 답을 구할 수 있다. 문제에서 X가 1,000,000,007의 큰 수 이므로 일반적인 제곱을 하면 범위 초과가 발생하므로 mod연산과 분할 정복을 이용하여 제곱값을 구한다. 코드 #include const int MOD = 1'000'000'007; using namespace std; // a를 b번 곱하고 c로 나눈 값 long long power(long long a, long long b, long long c) { if (b == 0) { return 1; } if (b == 1) { return a % c; } l..
