ABC 401-500/ABC428D - 183184 - 競技プログラミング用 知識集積所

---

問題

ABC428D

必要知識

B以下レベルの内容は省略

• 特になし

考え方

数字をそのまま連結するのは、難しい。
1つ1つなら文字列にして連結する手はあるが、しかし全てを1つずつチェックしていてはTLE。
ということで、難しいけど仕方なく頑張ってくっつけていく。

例えばCが20でDが2000である場合、C+xは21から2020までになる。
これを「21から99まで」「100から999まで」「1000から2020まで」にわければ、その前にCをくっつけるのは「Cの100倍を足す」「Cの1000倍を足す」「Cの10000倍を足す」で済む。
C+Dは最大でも10桁なので、このように桁数にわけて処理すれば、各範囲内での平方数の個数を合計する問題として時間内に間に合うようになる。

L以上R以下の平方数の個数は、R以下の平方数の個数から、L-1以下の平方数の個数を引けばよい。
R以下の平方数の個数は、√Rの整数部分を見ればよい。

以上の処理を適切な順番に実行するように実装すればよい。

解答例

解答例

注意点

平方根の計算にsqrt()※を用いない

sqrt()※は内部でdoubleを使って計算しているため、10^16くらいになると桁落ちしてしまう。
sqrtl()※を用いること。
もしくは、二分探索※で自力で平方根を計算する。

別解