오일러 정리에 의하면
$a^{\varphi(n)} \equiv 1\pmod{n}$
입니다. 이때 $\varphi(n)$(오일러 피 함수)은 1부터 $n$까지의 수 중 $n$과 서로소인 수의 개수입니다.
$a$와 $n$이 서로소일 때만 가능합니다.
오일러 피 함수 구하기
더보기
$\varphi(n)$ 는 몇가지 특징이 있어 생각보다 쉽게 구할 수 있습니다.
- $p$가 소수일 때 $\varphi(p) = p-1$
- $\varphi(pq)= \varphi(p) * \varphi(q) $
- $ \varphi(p^n)=p^n - p^{n-1} $
이를 잘 이용하면 소인수분해를 이용해서 구할 수 있습니다.
오일러 정리를 이용하면 모듈러 연산에서 나눗셈을 할 수 있습니다.
$\begin{matrix} &a^{\varphi(n)} &\equiv& 1&\pmod{n} \\ \Rightarrow &a^{\varphi(n) - 1} &\equiv& a^{-1}&\pmod{n} \end{matrix}$
즉 $x/y = x*y^{-1}=x*y^{ \varphi(n) - 1}$이 되고 $y$에 $ \varphi(n) - 1$승을 해서 구할 수 있습니다.
#define ll long long
#include<iostream>
using namespace std;
ll pow(ll n, ll p, ll m) {
if (p == 0) return 1;
if (p == 1) return n;
ll tmp = pow(n, p / 2, m);
if (p % 2 == 0) return tmp * tmp % m;
else return tmp * tmp % m * n % m;
}
int main() {
ll x, y, n, oiler = 1;
cin >> x >> y >> n;
ll temp_n = n;
//오일러 피 함수 계산
for (ll i = 2;i <= temp_n;i++) {
if (temp_n % i == 0) {
ll count = 0, cur_pow = 1;
while (temp_n % i == 0) { temp_n /= i; count++; cur_pow *= i; }
oiler *= cur_pow - (cur_pow / i);
}
}
cout << (x * pow(y, oiler - 1, n)) % n;
return 0;
}
'PS - 알고리즘' 카테고리의 다른 글
백준 13573 - 동전 뒤집기 3 (1) | 2024.03.23 |
---|---|
SOS dp (0) | 2024.03.21 |
백준 14854 - 이항 계수 6 (0) | 2024.03.16 |
x^n 을 O(log n)에 구하기 (0) | 2024.03.16 |
N!에서 소수 p 등장 횟수 구하기 (0) | 2024.03.16 |