999999999999999999/2**18*2**18=1e+18になる話

#Rust  #Python 

どうやってもabc400のC問題がWAで通らず、その後解説のうち1つを見ても同じことやってんじゃん！！！となったわけでさらに泥沼のデバッグをしていたわけだが、そこで気づいた。\(N\) に

999999999999999999

を入力すると、この解説プログラムだと

1207106780

を出力するが、私のだと

1207106781

を出力することに。なんかちがう

そこで、イテレートする a ごとに加算する値を確認していったところ a=18 で異なる値となっていることに気づいた。解説との違いとしては、私は浮動小数点型（Rust の f64）を使って計算していたのだが、この点に関して桁数の多いPythonで見てみてもおかしなところは特になさそうに見えた：

>>> 999999999999999999/2**18
3814697265625.0

これは綺麗に平方根をとることもできる

>>> sqrt(3814697265625)
1953125.0

なんとなく 2**18 を掛け直してみた

>>> 999999999999999999/2**18*2**18
1e+18

は？………つまり…どういうことだってばよ？

>>> Decimal(999999999999999999)/Decimal(2**18)
Decimal('3814697265624.999996185302734')

すみません、浮動小数点誤差を舐めてました…はい。

整数で計算できるなら整数で計算すべきですね。ということでこれを修正して、

let max_squared_b = n / left;
let max_b = (max_squared_b as f64).sqrt() as i64;
cnt += (max_b + 1) / 2;

…WA！！なんで！？！？

解説では C++ の isqrt を使っているが、 Rust の isqrt は Rust 1.84 からなので、 Rust 1.70.0 (250406時点) の atcoder ではまだ使えない。ならどうするか

[dependencies]
num = "=0.4.1"

use num::integer::Roots;
...
let max_b = max_squared_b.sqrt();

とすれば整数型の正確な小数点切り捨て平方根が使えるわけですね！！（もしくは二分探索で平方根計算）

やっと通ったので、以上……。コンテスト終わってから3,4時間経ってるんですけど……