목록페르마의 소정리 (1)
블로그 옮겼습니다
제5회 kriiicon 연습 세션 C번 다항식 계산
https://oj.uz/problem/view/KRIII5P_2 \(0\le{N}\le{10^6},\,1\le{P}\le{10^3}\)N차 다항식 \(f(x) = a_{N}x^{N}+\cdots+a_{1}x+a_{0}\) 과 소수가 주어진다.이 때 \(f(0)\,mod\,P,\,f(1)\,mod\,P,\,\cdots,\,f(P-1)\,mod\,P\) 를 각각 구하는 것이다. 우선 가장 naive 하게 생각을 해보면f(x) 를 구하는데에 걸리는 시간을 생각해 보면 빠른 N제곱을 하는데에 O(lgN) 이 걸리기 때문에각 항을 계산하는데에는 O(lgN) 이걸리는데 항의 수가 N개 이기 때문에 O(NlgN) 이 걸린다는것을 알 수가 있다.그런데 P가지의 x 에 대해 계산을 하기 때문에 O(NPlgN) 의 시간..
Algorithm/Problem Solving
2017. 4. 30. 09:06