SRM 735 + TCO18 Algorithm R2C

x(x-1)≡0のとき、Mの素因数が中途半端に含まれてるとMで割り切れないので、xとx-1は互いに素、というのをようやく理解した

2018-06-26 23:27:34

SRM廃人はSRMに出るしかないので、TCO同時開催されても出られないんだよな。別々にやるとは思わなかった。

2018-06-26 23:30:57

今回の500でextgcdを使ってax+by=gcd(a,b)を満たすx,yを求める系なやつのことを中国剰余定理と思ってたけど違って、ATC001でNTT（剰余環を利用したFFT）の時にGarnerのアルゴリズムを使ったのが中国剰余定理だ

2018-06-27 00:14:58

はてなブログに投稿しました #はてなブログ SRM 735 DIV1 Medium QuadraticIdentity - けんちょん (drken) の競プロ精進記録 drken1215.hatenablog.com/entry/2018/06/…

2018-06-27 01:31:00

確かに、beet たんが「中国剰余定理はオーバーキル」と言っていたんはそれはそうなん。

2018-06-27 01:49:45

tourist は普通に中国剰余定理のコード貼ってたん(￣O￣;) 確かにライブラリあったらペタリが早いのんな。

2018-06-27 09:10:36

レート確定してた(1491→1611)＆黄色復帰 naoyat.hatenablog.jp/entry/SRM735

2018-06-27 10:25:01

"Mの素因数が、xとx-1のどちらかに含まれる" が、互いに素でないケースもあるのでは

2018-06-27 14:31:03

メモ SRM 735 DIV1 Hard codeforces.com/blog/entry/602…

2018-06-27 20:52:44

TCOボーナスで黄色になってた

2018-06-27 23:32:43

@hotpepsi xとx-1って、xにどんな整数が来ても絶対に互いに素ですよね

2018-06-27 23:35:49

@naoya_t たしかに...それはさておき、SRM 735 div1 med難しい

2018-06-27 23:56:08