본문으로 건너뛰기
김신건의 로그

Polynomial Division, Kitamasa의 O(K² log n) 항 계산

피보나치 점화식 a_n = a_{n-1} + a_{n-2}의 n번째 항을 O(K² log n)에 계산. 특성다항식 x² - x - 1로 x^n mod f를 이진법 거듭제곱으로 빠르게 구해 선형결합.

메타데이터

ID polynomial-division-kitamasa
카테고리 algorithm
버전 v4
길이 12.0s (12000ms)
구성 11 elements · 5 chapters · 4 effects
태그 #algorithm #math #kitamasa #polynomial #linear-recurrence

본문에 삽입

```anim:polynomial-division-kitamasa
{}
```

이 애니메이션을 사용하는 글 (1)

사이트 검색 / 명령어

검색

스크롤 = 확대/축소 · 드래그 = 이동 · 0 = 원래 크기 · ESC = 닫기