[중고딩문제] 정수론 문제인데 어떤 식으로 접근해야 될지 힌트좀

[익명(211.207)]

임의의 자연수 N과 M이 주어져 있다. A^B를 A의 B승이라고 할 때, 수열 N, N^N, N^(N^N), N^(N^(N^N)), ... 의 수들을 M으로 나눈 나머지는 수열의 어느 지점부터 항상 일정한 값을 가진다. N과 M이 주어져 있을 때, 이 일정한 나머지 값을 계산하라.

오일러 파이 함수 쓰는 문제라는데 정수론 문제를 거의 안 풀어봐서 어떻게 접근해야 될 지조차 감이 안 잡힘

힌트 좀 줄 사람

[익명(106.101)]

일정해지는 건 파이 잘쓰면 증명될것 같은데, 어떤 값인지는 바로 안 떠오 - dc App

[익명(211.207)]

프로그래밍 문제라 어떤 값인지는 알고리즘 짜서 돌리면 되고, 그 알고리즘 짜는 데 논리가 중요해서

[익명(106.101)]

recursive 하게 접근하면 될듯 M으로 나눈 나머지를 고려할때 승수를 piM으로 나눈 나머지를 고려하게 되고 그럼 이것도 탑처럼 쌓여있으니까 승수를 pi pi M으로 나눈 나머지로 고려하게 되고 … 이런 식으로 가다보면 piM < M이기 때문에 1이 될 거임 그럼 계산됨 일정한 값이 나오도록 N M 이 주어지니까 그건 증명할 필요 없을듯 , 일정하게 안되는 경우도 있을것 같아 - dc App

[익명(125.128)]

N의 x제곱을 M으로 나눈 나머지를 구하려면 x를 phi(M)으로 나눈 나머지를 구하면 된다는 걸 이용하셈. 귀납적으로 x를 phi(M)으로 나눈 나머지 r을 구했을때 N^r을 M으로 나눈 나눈 나머지는 r의 이진법표현을 통해 구하면 빨리 구해짐. 다만 M이 클 때 phi(M)을 구하는게 어려워서 이시간이 전체 알고리즘에서 제일 긴 시간을 차지할 것 같음.