ACL の math の解説をするよ - えびちゃんの日記ACL (AtCoder Library) の内部実装を知りたい人向けの記事です。 お友だちに「ねーね、ACL のこの関数ってどういう仕組みなの？ 知ってたりしない？」と聞かれたとき、「え... なんかほら、わかんないけど、魔法で動くからいいんだよ」としか言えないと情けない気がしません？ しました。なので書きます。 こういうシチュエーションはなくても、何かを実装したいときに「あ、これ ACL の実装のやつと同じ発想じゃん」となることはありえるので、知っていて損はないかなと思います。 めちゃくちゃ長くなったので、一度に全部読むのには適さないかもしれません。 数式部分の LaTeX コードなども含めて数えられていますが、26000 文字を超えています。 全体像 個別の説明 internal::safe_mod internal::barrett Barrett reduction の話 正当性
