naoya_t@hatenablog

いわゆるチラシノウラであります

Mathematics

MathMash Round 19

6/11 2:25-4:25am JST ABCの後に寝落ちして、ちょうど目が覚めたところでTLで目に飛び込んできたので(急遽アカウントを作って)出てみた 7完 (ABCDEF-H) 9816点で8位 1248(+248) EとHはズルしてる

DFT(離散フーリエ変換)とNTT(数論変換:整数(剰余環)を用いたDFT)

先日ARC埋めの一環でATC001のC問題(高速フーリエ変換)を解いたのだけれど、こういう畳み込み問題はDFT(discrete Fourier transform;離散フーリエ変換)の代わりに NTT(number-theoretical transform;数論変換)という "整数(剰余環)を用いたDFT" で…

拡張ユークリッド互除法の話

先日の連分数の計算と拡張ユークリッド互除法って少し似てるなと思ったというメモ。(連分数の計算で次の項を求める時にやっている操作ってユークリッドの互除法そのものだし当然か)拡張ユークリッド互除法というのは、 を満たす を求める方法。 を で割れば…

連分数 (continued fraction)

連分数 - WipikediaこないだのJune Long ChallengeのEuler Sumを考えてる時に Mark Jason Dominus氏のスライド Arithmetic with Continued Fractions を読んだ時のメモ。連分数とかいじるのって多分昔SICPを読んだ時以来。