【AtCoder】ABC 428 D - 183184

2025-10-22

AtCoder/ABC/D問題 AtCoder/ABC/400点問題 AtCoder/水Diff AtCoder/NoviSteps/1D AtCoder/数学/整数論/平方数 AtCoder/数え上げ競技プログラミング

実行時間制限: 2.5 sec / メモリ制限: 1024 MiB / Difficulty: 1239 / NoviSteps: 1D / 配点: 400 点

問題概要

正整数 $x,y$ に対して $f(x,y)$ を以下で定義する。

十進表記の $x,y$ をそれぞれ文字列として解釈しこの順に連結して得られる文字列を $z$ とする。 $z$ を十進表記の整数として解釈したときの値を $f(x,y)$ とする。

正の整数 $C, D$ が与えられるので、以下を満たす整数 $x$ の個数を求めよ。

$1 \leq x \leq D$
$f(C, C+x)$ は平方数である

ただし、 $T$ 個のテストケースが与えられるので、それぞれについて答えを求めること。

制約

$1 \leq T \leq 3 \times 10^5$
$1 \leq C \leq 2 \times 10^8$
$1 \leq D \leq 5 \times 10^9$
入力される値はすべて整数

考察

まずは、 $f(C, C+x)$ の値が取りうる範囲を考えよう。

$C+x$ の部分が $k$ 桁の数であるとき、 $f(C, C+x)$ は次のように表せる。

\begin{equation} f(C, C+x) = C \times 10^{k} + C + x \tag{1} \end{equation}

ここで、 $C + x$ が $k$ 桁の数であるための条件 :

\begin{equation*} 10^{k-1} \leq C + x \leq 10^{k} - 1 \iff 10^{k-1} - C \leq x \leq 10^{k} - 1 - C \end{equation*}

と、問題文の $1 \leq x \leq D$ という条件の共通部分を取ると、 $x$ の取りうる範囲は以下の $l, r$ を用いて $l \leq x \leq r$ と表せる。

\begin{align*} l & = \max(1, 10^{k-1} - C) \\ r & = \min(D, 10^{k} - 1 - C) \end{align*}

ただし、 $l > r$ のときはこのような $x$ は存在しない。

上記の範囲を $x$ が動くとき、 $f(C, C+x)$ の値の範囲は式 $(1)$ から以下のようになる。

\begin{equation} C \times 10^{k} + C + l \leq f(C, C+x) \leq C \times 10^{k} + C + r \tag{2} \end{equation}

あとは、この範囲内で平方数となる整数の個数を求めればよい。

ある正整数 $x$ に対して、 $x$ 以下の平方数の個数は $\lfloor \sqrt{x} \rfloor$ であるという事実を用いると、式 $(2)$ の範囲内で平方数となる整数の個数は以下のようになる。

\begin{equation*} \lfloor \sqrt{C \times 10^{k} + C + r} \rfloor - \lfloor \sqrt{C \times 10^{k} + C + l - 1} \rfloor \end{equation*}

$C+x$ は最大 $10$ 桁であるから、これを $k = 1, 2, \ldots, 10$ について全て足し合わせたものが求める答えとなる。

実装例

$\lfloor \sqrt{x} \rfloor$ の計算は二分探索でも実装できるが、公式解説のものを拝借して実装すると実質 $O(1)$ で計算することができる。

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5.#define repe(i, start, end) for (auto i = (start); (i) <= (end); (i)++)
6. 
7.using ll = long long;
8. 
9.ll floor_sqrt(ll x)
10.{
11.    ll y = sqrt(x);
12.    while (y * y > x)
13.        y--;
14.    while ((y + 1) * (y + 1) <= x)
15.        y++;
16.    return y;
17.}
18. 
19.// ======================================== //
20. 
21.int main()
22.{
23.    int T;
24.    cin >> T;
25. 
26.    vector<ll> pow10(11, 1);
27.    rep(i, 1, 11) pow10[i] = pow10[i - 1] * 10;
28. 
29.    auto solve = [&]() -> ll
30.    {
31.        ll C, D;
32.        cin >> C >> D;
33. 
34.        ll ans = 0;
35.        repe(k, 1, 10)
36.        {
37.            ll l_x = max<ll>(1, pow10[k - 1] - C);
38.            ll r_x = min<ll>(D, pow10[k] - 1 - C);
39.            if (l_x > r_x)
40.                continue;
41. 
42.            ll l_val = pow10[k] * C + C + l_x;
43.            ll r_val = pow10[k] * C + C + r_x;
44. 
45.            ans += floor_sqrt(r_val) - floor_sqrt(l_val - 1);
46.        }
47. 
48.        return ans;
49.    };
50. 
51.    while (T--)
52.    {
53.        cout << solve() << endl;
54.    }
55. 
56.    return 0;
57.}