2018-07-12から1日間の記事一覧
数え上げ問題
包除原理
各kに対して
数学(整数問題)
バケット
調和級数
約数系包除
前処理
AtCoder
unrated公式コン
AtCoder600点
制約:数値が10^6以下
エラトステネスの篩
添字GCD畳み込み
高速メビウス変換
メビウス関数
そのまま覚えたいシンプル設定の中堅以上の典型問題
メビウスの反転公式
という制約の意味に気がつくのにかなり時間がかかった。これのおかげで「 の中に の倍数が何個あるか」というのが、 ではなく でできる。 問題へのリンク 問題概要 個の相異なる整数 と、整数 が与えられる。各 に対して、 のうち と互いに素なものが何個あ…
問題へのリンク 問題概要 整数 があたえられる。 進法で有理数 p/q を小数で表したときに有限小数となるような最小の 2 以上の整数 を求めよ。 制約 < < 考えたこと とりあえず p/q を約分しておく。 そして、q を素因数分解したときの、指数部を全部 1 にし…