kyume   1년 전

테스트 케이스는 전부 시간 내에 통과합니다. 제출시엔 25%에서 틀렸습니다가 뜹니다.

이틀간의 시도 끝에, given a, b, c에 대하여, 답이 aa^f(a,b,phi(phi(c))mod c임을 알게 되었습니다.

a -> a^a -> a^a^{1+a} -> a^a^{1+a+a1+a}와 같이 ㅁ+a^ㅁ의 꼴이 반복되는 규칙성을 보고 코드를 작성했습니다.

함수 f(a, b, p)는, a == 1 or b == 1 or p == 1 -> 1, otherwise f(a, b-1, p) + af(a, b-1, phi(p))을 반환하는 함수입니다.

위와 같은 방식으로 재귀함수를 구현하고, phi값을 전처리하고, 재귀함수의 반환 값을 메모지제이션 하였습니다.

이틀간 시도해 보았지만, 도저히 어떤 부분이 문제가 되는지 전혀 감이 잡히지 않습니다. 도움 부탁드려요.

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