16214번 - N과 M
우선 처음 제출했던 코드입니다.
시간초과 날줄은 알았는데 일단 짜봤습니다. 제출을 해보니 역시 시간초과가 났습니다.
질문의 글을 읽고, 질문을 통해 오일러의 phi함수를 이용해보려고 코드를 짰습니다.(저 코드는 아닙니다)
그런데 작동이 잘 안하길래 처음 제출했던 코드를 다시 작동해보니 예제의 3번째 28,43이 제대로 나오지 않는 것입니다 (왜 이제 눈치챘는지 모르겠습니다.)
pow함수는 N^N을 구하는 함수인데요
코드 제대로 짠 것 같은데 뭐가 문제일까용...
(n ^ (n ^ n)) mod m 이 (n ^ ((n ^ n) mod m)) mod m 이랑 같을까요?
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이 나올 수가 없으니 잘못 생각하고있음을 알았습니다..
잘 읽어보세요 답이 써있습니다
제가 기록을 잘못하고있었네요 모듈러계산은 이제 잘 작동해서 말씀하신 피함수를 적용하려합니다.
오일러의 피함수가 맞지 않나요? 예제의 3 4의 경우 4를 피함수에 넣으면 2 여서 답이 3이 못나오는데 어떤부분이 잘못된건가요
댓글을 작성하려면 로그인해야 합니다.
dlftls38 4년 전
우선 처음 제출했던 코드입니다.
시간초과 날줄은 알았는데 일단 짜봤습니다. 제출을 해보니 역시 시간초과가 났습니다.
질문의 글을 읽고, 질문을 통해 오일러의 phi함수를 이용해보려고 코드를 짰습니다.(저 코드는 아닙니다)
그런데 작동이 잘 안하길래 처음 제출했던 코드를 다시 작동해보니 예제의 3번째 28,43이 제대로 나오지 않는 것입니다 (왜 이제 눈치챘는지 모르겠습니다.)
pow함수는 N^N을 구하는 함수인데요
코드 제대로 짠 것 같은데 뭐가 문제일까용...