ghost_diht   1년 전

안녕하세요, 1629번 관련해서 질문이 있는데요,
페르마 소정리를 생각해 보면 a^(b%(c-1)) 만 하면 될 것 같은데
왜냐하면 b = (c-1)*x + (b%(c-1))이라고 생각하면 a^((c-1)*x) % c는 그냥 1일거잖아요(x는 어떤 정수)
그런데 몇몇 예제에서 오답이 나오더라구요
혹시 제 생각에 틀린 부분이 있는지, 아니면 제 코드가 어디가 잘못됐는지 알려 주실 수 있으면 정말 감사할 것 같습니다!
(우선 그냥 분할정복으로 '맞았습니다!'는 띄웠는데 더 잘 풀 방법이 있을 것 같아서 시도한 방법입니다)

qawbecrdtey   1년 전

페르마 소정리를 사용하려면 나누는 수가 소수여야 합니다.

ghost_diht   1년 전

헉 그냥 a랑 서로소이기만 하면 되는 게 아니었군요.... 감사합니다!! 제가 어중간하게 알고 있었네요...

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