文学徒が競プロをするブログ

競技プログラミングの精進を記録していきます

Codeforces Round #701 (Div. 2) C. Floor and Mod

限りなく本質に近づいていたのに、そこから40分あっても解けなかった。めっちゃ悔しい。こういうやつを淡々と機械的に詰め切れるようになりたい。

それはそれとしてB問題みたいなこどふぉありがちパズルゲームめっちゃ嫌い。最近気づいたけど、数学ゲーよりパズルゲーの方が時間かかってる気がします。

問題設定

$1 \leq a \leq x$ かつ $1 \leq b \leq y$ のとき、 $\frac{a}{b} = a \bmod b$ となる $(a, b)$ の組の個数を求めよ

解法(自力で行けるところまで)

見た目からしてあからさまに式変形してくださいと言っている問題なので、やる。

$a \bmod b = M$ とおく。

$\frac{a}{b} = M ... M$

$a = M \times b + M$

$a = M(b+1)$

$a \bmod b = M$ から、 $M \lt b$ として、

$a = M(b+1)$ (ただし $M \lt b$ ) となる。

よって、 $a$ は $(b+1)$ の倍数かつ、その係数を $M$ とおくと、 $M \lt b$ ということになる。

ここまではまあ来れて、bを一つずつ決め打って全探索してしまえば答えが出ることがわかる。

$\sum_{b=2}^{y} min(\frac{x}{(b+1)}, (b-1))$

綺麗に定式化するとこんな感じ。

しかし制約は $1 \leq x, y \leq {10}^{9}$ なので、ナイーブなやり方ではだめ。

ここまで来て解けないのなんだかなあ。

式をよく見ると、 $\frac{x}{b+1} \lt b$ となるような $b$ までは、答えは全部 $b-1$ の連番なので、そこまでの計算を省略できる。
めんどくせーとか言いながらにぶたんを書いた。

これでminを考えなくても良くなって、 $\frac{x}{b+1} \lt b$ となるような $b$ を $c$ とおくと、

$\sum_{b=c}^{y} \frac{x}{(b+1)}$

の値を後は求めればいい。ここまではコンテスト時間内に来ました。

解説見た

解説見た。そもそもbを固定するのは筋が悪いっぽい。

$b-1 \geq M$ より、 $M$ の最大値は $b-1$ となる。
したがって $b+1 > M$ となるので、 ${M}^{2} \lt M(b+1) \leq x$ から、 $M \leq \sqrt{x}$ である。

要は $M$ を $\sqrt{x}$ まで決め打って求めればいい。

あとは決め打ったときの求め方ですが、頑張って式変形しましょう。

まず $b$ の範囲を求めます。

$M \lt b \leq y$ なので、 $M+1 \leq b \leq y$ となります。最大値 $y$ で最小値が $M+1$ なので、 $b$ の個数は $y-(M+1)+1 = y-M$ です。

次に $a$ の範囲ですが、 $a$ は $b$ と $M$ の式で表せます。

$M(b+1) \leq x$ から $b \leq x/m-1$ となるので $b$ の最大値は $x/m-1$ となります。

また $M+1 \leq b$ なので $M(M+2) \leq M(b+1)$ と置けて $M+1 \leq b$ となります。

最大値が $x/m-1$ で最小値が $M+1$ なので、 $a$ から求められる $b$ の個数は $x/m-1 - (M+1) +1 = x/m-1-M$ です。

あとはこの小さい方を取れば良く、 $max(0, min(y, x/M-1)-M)$ となるので、解けます。