dlftls38   4년 전

우선 처음 제출했던 코드입니다.

시간초과 날줄은 알았는데 일단 짜봤습니다. 제출을 해보니 역시 시간초과가 났습니다.


질문의 글을 읽고, 질문을 통해 오일러의 phi함수를 이용해보려고 코드를 짰습니다.(저 코드는 아닙니다)

그런데 작동이 잘 안하길래 처음 제출했던 코드를 다시 작동해보니 예제의 3번째 28,43이  제대로 나오지 않는 것입니다 (왜 이제 눈치챘는지 모르겠습니다.)

pow함수는 N^N을 구하는 함수인데요


코드 제대로 짠 것 같은데 뭐가 문제일까용...

sait2000   4년 전

(n ^ (n ^ n)) mod m 이 (n ^ ((n ^ n) mod m)) mod m 이랑 같을까요?

dlftls38   4년 전

pow함수의 순간순간 상태를 찍어보니 그 문제일 것 같았습니다....

그저 제곱이아닌 N^N이라 엄청 크게 불어나 long long으로는 안되고.. 어떤 방식을 써야하는 것인가요 phi함수도 어디에 적용해야할지 잘 모르겠습니다

n^n^n^n^...(mod m) ->  n^n^n^n^...(mod phi(m)) 적용이 되신다고 하셔서 저는 m대신 phi(m)으로 되는구나 생각했는데

m이 4면 phi(m)은 2인데 예제의 3 4 답은 3이라서 mod 2면 3이 나올 수가 없으니 잘못 생각하고있음을 알았습니다..

sait2000   4년 전

잘 읽어보세요 답이 써있습니다

dlftls38   4년 전

제가  기록을 잘못하고있었네요 모듈러계산은 이제 잘 작동해서 말씀하신 피함수를 적용하려합니다.

오일러의 피함수가 맞지 않나요? 예제의 3 4의 경우 4를 피함수에 넣으면 2 여서 답이 3이 못나오는데 어떤부분이 잘못된건가요

댓글을 작성하려면 로그인해야 합니다.