AtCoder 🟡 ABC428D 183184

題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 🟡 ABC428D 183184

Problem Statement

題目簡述

定義 $f(x, y)$ 為將正整數 $x$ 和 $y$ 的十進位表示串接後得到的整數（例如 $f(3, 14) = 314$）。

給定正整數 $C$ 和 $D$，求滿足 $1 \le x \le D$ 且 $f(C, C+x)$ 為完全平方數的 $x$ 的個數

Constraints

約束條件

• $1 \le C \le 2 \times 10^8$
• $1 \le D \le 5 \times 10^9$

---

思路：按位數分段枚舉 + 區間完全平方數計數

問題轉化

令 $y = C + x$，則 $x \in [1, D]$ 等價於 $y \in [C+1,\, C+D]$。

串接函數 $f(C, y)$ 的數學意義：若 $y$ 的十進位有 $\ell$ 位，則

$$f(C, y) = C \cdot 10^{\ell} + y$$

問題變成：有多少 $y \in [C+1,\, C+D]$ 使得 $C \cdot 10^{\ell} + y$ 為完全平方數？

固定位數後的區間計數

核心觀察

對於固定的位數 $\ell$，$y$ 的範圍為 $[10^{\ell-1},\, 10^{\ell}-1]$（即所有 $\ell$ 位正整數）。將此範圍與 $[C+1,\, C+D]$ 取交集，得到有效的 $y$ 範圍 $[\text{lo},\, \text{hi}]$。

此時 $f(C, y) = C \cdot 10^{\ell} + y$ 隨 $y$ 單調遞增，所以目標值的範圍也是一段連續區間：

$$L = C \cdot 10^{\ell} + \text{lo}, \quad R = C \cdot 10^{\ell} + \text{hi}$$

問題最終歸結為：$[L, R]$ 中有多少個完全平方數？

區間完全平方數計數

經典技巧

$[L, R]$ 中的完全平方數個數 $= \lfloor\sqrt{R}\rfloor - \lceil\sqrt{L}\rceil + 1$（若結果為負則為 $0$）。

其中：

• $k_{\max} = \lfloor\sqrt{R}\rfloor$：用 isqrt(R) 計算
• $k_{\min} = \lceil\sqrt{L}\rceil$：用 isqrt(L - 1) + 1 計算（因為 $\lceil\sqrt{L}\rceil = \lfloor\sqrt{L-1}\rfloor + 1$ 對非完全平方的 $L$ 成立，而對完全平方的 $L$ 也是正確的）

精度陷阱

直接使用浮點數的 math.sqrt 會有精度問題（$C \cdot 10^{\ell} + y$ 可達約 $2 \times 10^{18}$），必須使用 Python 的 math.isqrt（整數精確平方根）。

枚舉位數的範圍

$y$ 的最小值為 $C + 1$，最大值為 $C + D$，因此 $\ell$ 的範圍為 $[\text{len}(C+1),\, \text{len}(C+D)]$。由於 $C \le 2 \times 10^8$、$D \le 5 \times 10^9$，$y$ 最大約為 $5.2 \times 10^9$，所以 $\ell$ 最多為 $10$，枚舉量極小。

總結

對每組測資，枚舉 $y$ 的位數 $\ell$（至多約 $10$ 種），對每個 $\ell$ 計算有效 $y$ 範圍並用整數平方根求區間內完全平方數個數，累加即為答案。每組測資 $\mathcal{O}(\log(C+D))$。

複雜度分析

• 時間複雜度：$\mathcal{O}(T \cdot \log_{10}(C + D))$
• 空間複雜度：$\mathcal{O}(\log_{10}(C + D))$（預處理 $10$ 的冪次表）

---

Code

from math import isqrt

pow10 = [1]
for _ in range(1, 20):
    pow10.append(pow10[-1] * 10)


def solve():
    C, D = map(int, input().split())

    ans = 0
    # 枚舉 y = C + x 的十進位長度
    # C + 1 <= (y = C + x) <= C + D
    for ln in range(len(str(C + 1)), len(str(C + D)) + 1):
        lo = max(C + 1, pow10[ln - 1])
        hi = min(C + D, pow10[ln] - 1)
        if lo > hi:
            continue
        # 得到滿足的 f(C, y) 的範圍 [L, R]
        L = C * pow10[ln] + lo
        R = C * pow10[ln] + hi
        # 計算滿足的 f(C, y) = k^2 的 k 的個數
        # 注意這裡直接用 floor(sqrt(R)) 以及 ceil(sqrt(L)) 會有精度問題
        k_max = isqrt(R)  # floor(sqrt(R))
        k_min = isqrt(L - 1) + 1  # ceil(sqrt(L))
        ans += max(0, k_max - k_min + 1)

    print(ans)


if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        solve()