x/y (mod n) 계산

오일러 정리에 의하면

$a^{\varphi(n)} \equiv 1\pmod{n}$

입니다. 이때 $\varphi(n)$(오일러 피 함수)은 1부터 $n$까지의 수 중 $n$과 서로소인 수의 개수입니다.

$a$와 $n$이 서로소일 때만 가능합니다.

 

오일러 피 함수 구하기

$\varphi(n)$ 는 몇가지 특징이 있어 생각보다 쉽게 구할 수 있습니다.

1. $p$가 소수일 때 $\varphi(p) = p-1$
2. $\varphi(pq)= \varphi(p) * \varphi(q) $
3. $ \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;
}