:: 게시판
:: 이전 게시판
|
- PGR21 관련된 질문 및 건의는 [건의 게시판]을 이용바랍니다.
- (2013년 3월 이전) 오래된 질문글은 [이전 질문 게시판]에 있습니다. 통합 규정을 준수해 주십시오. (2015.12.25.)
통합규정 1.3 이용안내 인용"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
17/11/02 22:15
long long fexp(long long base, long long exp, long long mod) {
if (exp == 1) return base; long long res = fexp(base, exp/2, mod); res = res * res % mod; if (exp % 2) res = res * base % mod; return res; } 이걸로 돌려보세요. 시간복잡도 O(log p) 니까 순식간에 나올겁니다.
17/11/02 22:21
그냥 드는 생각으로는... 로그 함수를 쓰건 pow를 쓰건...
a^q > n 이 되는 최소한의 q를 찾고, (a^q)/n 을 구한 다음에 [이걸 w라고 치고] w^(p/q)*a^(p%q) % n 하면 어떨까요?
|