[백준 16214] N과 M [C]

백준 - 16214

---

풀이

오일러의 정리를 이용해서 풀이하는 문제다.

위키백과 - 오일러 피 함수

이나... 자료가 너무 부족하다.

오일러의 정리에 대해 자료를 찾던 도중 다음과 같은 자료를 찾았다.

• a와 n이 서로소이면, a^m ≡ 1 mod n에서 m = EPF(n)을 만족하는 정수 m이 적어도 하나 존재한다.
• a (mod n)에 대한 차수가 위 식의 m이 될 수 있다.

 (N ^ f( N, EPF(M) ) ) % M을 재귀호출해 찍었다. 풀이했다.

 

입력받거나 전달받은 N과 M 둘 중 하나가 1일 때, 1을 반환해주면 위 식의 계산에 따라 원하는 결과를 얻을 수 있다.

단, 제곱을 구하는 과정에서 long long으로도 담을 수 없는 수가 나온다.

(N^(N^N)) mod M != (N^((N^N) mod M)) mod M 이므로, M이 아닌 EPF(M)으로 나눈 나머지를 이용해 구했다.

 

하면 될줄 알았으나.. 20%이후로 틀렸다고 뜬다.

찾아본 결과  (N ^ f( N, EPF(M) ) ) % M에 EPF(M)을 더해준 값을 가지고 제곱을 해줘야 된다. 

이 부분에 대한 자세한 설명은 백준 질문 게시판에 올라온 글을 참고하면 좋을 듯 하다.

---

소스코드

#include <stdio.h>
int EPF(int n){
    int euler = n;
    for (int p = 2; p*p <= n; p++){
        if (n % p == 0) euler = euler/p *(p - 1);
        while (n % p == 0) n = n/p;
    }
    return n == 1 ? euler : euler/n *(n - 1);
}

int NM(int n, int m){
    if (n == 1 || m == 1) return 1;
    long long A = n;
    int B = NM(n, EPF(m)) + EPF(m), result = 1;
    while (B){
        if (B & 1) result = result*A %m;
        B >>= 1;
        A = A*A %m;
    }
    return result;
}

int main(){
    int T, N, M, result;
    scanf("%d", &T);
    while (T--){
        scanf("%d %d", &N, &M);
        printf("%d\n", NM(N, M) %M);
    }
}

---

출처 및 참고자료

16214번: N과 M

오일러 피 함수 - 위키백과, 우리 모두의 백과사전

제 5 장 암호학의 수학기초

글 읽기 - 문제 풀이 방법에 대한 감이 잡히지 않습니다..