search

kmyk-jikka / Jikka

an automated solver for problems of competitive programming
https://kmyk-jikka.github.io/Jikka/playground
Apache License 2.0
152 stars 11 forks source link

セグメント木や累積和に GCD や LCM を載せる #152

Closed kmyk closed 2 years ago

kmyk commented 2 years ago

いまは半群として (ℤ, +), (ℤ, min), (ℤ, max) しか使ってないけれど、gcd, lcm もほしい 特に <O(N), O(1)> GCD を貼れるとなんだかうれしい

hotman78 commented 2 years ago

segment tree についてgcdは償却計算量となるのでそこまでうれしくはなさそうです、別のデータ構造として追加するのはとても賛成です

hotman78 commented 2 years ago

LCMに関してはオーバーフローが大きな問題になりそうですね...

hotman78 commented 2 years ago

LCMに関してはオーバーフローが大きな問題になりそうですね...

とりあえずこの問題は無視して作ります