[math] 素因数分解

[ei1333]

高速素因数分解

Description

ポラード・ロー素因数分解法(Pollard’s rho algorithm)

$O(N^{\frac 1 4})$ expected

File Name

src/math/primes/fast-prime-factorization.hpp

TODO

• [ ] 実装
• [ ] ドキュメント作成
• [ ] unit-test
• [ ] verify

note

• reference material
  • https://qiita.com/Kiri8128/items/eca965fe86ea5f4cbb98
• implementation
  • (url)
• 関連 issue / PR

  • 153 のために必要

• verify:
  • https://judge.yosupo.jp/problem/factorize

いつもの $O(\sqrt{N})$

Description

おれたちの $O(\sqrt{N})$

File Name

src/math/primes/prime-factorization.hpp

TODO

• [ ] 実装
• [ ] ドキュメント作成
• [ ] unit-test
• [ ] verify

note

いる？これ

エラトステネスの篩を利用した素因数分解クエリ

Description

前計算 $O(N \log \log N)$

クエリあたり $O(\log N)$

File Name

src/math/primes/sieve-of-eratosthenes.hpp

TODO

• [ ] 実装
• [ ] ドキュメント作成
• [ ] unit-test
• [ ] verify

note

• reference material
• implementation
• 関連 issue / PR
• verify:

[ei1333]

$O(\sqrt N)$ のやつも欲しいかも

[Luzhiled]

これは math/primes/~ ですかね