https://atcoder.jp/contests/abc162/submissions/14903598
- gcd=t の決め打ち
- 緩和した条件なら簡単に計算できる
- 降順に答えを求めるとメモ化が役に立つ
- 上記結果とメモ化した答えを足したり引いたりすることで設問の答えを得る
ではTLEするので、gcd=tとなる個数を決め打ちする考えで計算量を減らす。c(t)をgcd=tとなる個数とする。
とするとgcd=tとgcd=ptを含んでしまうが、g(t)を使って以下の式でc(t)を計算することができる。
c(1)からc(K)の計算は調和級数になっているので、c(K)から降順に求めてメモ化すればで済む。累乗を繰り返し二乗法にすれば各g(t)は
で計算できるので、全体計算量
になる。
