考察

\(C + x\) の桁数が \(d\) であるときを考えます．このとき，\(x\) の範囲は以下の \(2\) 範囲の共通部分として得られます．

• \(1 \leq x \leq D\)
• \(10^{d-1} - C \leq x \leq 10^d - 1 - C\)

\(L = \mathrm{max}(1, 10^{d-1} - C),\ R = \mathrm{min}(D, 10^d - 1 - C)\) とおいたとき，\(L > R\) であればそのような \(x\) は存在せず，\(L \leq R\) であれば \(L \leq x \leq R\) が範囲です．

\(C + x\) の桁数が \(d\) のときを考えているので，\(f(C, C+x) = C \times 10^d + (C+x)\) となります．したがって，\(C \times 10^d + C + L\) 以上 \(C \times 10^d + C + R\) 以下の範囲にある平方数の個数がこの範囲の答えになります．

\(k\) 以下の正の平方数の個数は \(\lfloor \sqrt{k} \rfloor\) なので，求める答えは \(\lfloor \sqrt{C \times 10^d + C + R} \rfloor - \lfloor \sqrt{C \times 10^d + C + L - 1} \rfloor\) となります．

\(\lfloor \sqrt{k} \rfloor\) を求めるにあたっては，二分探索で求めるよりも std::sqrt 関数を利用するほうが高速です．

以上の計算を \(d = 1, \dots, \lfloor \log_{10} (C+D) \rfloor + 1\) に対して行い，答えを足し合わせることで，全体の答えが求まります．

平方根の計算が定数時間として，時間計算量は \(O(\log(C+D))\) となり，十分高速です．

実装例 (C++)

#include <iostream>
using std::cin;
using std::cout;
using std::min;
using std::max;
#include <cmath>

typedef long long int ll;

// floor(sqrt(x))
ll f (ll x) {
	ll y = sqrt(x);
	while (y * y > x) y--;
	while ((y+1) * (y+1) <= x) y++;
	return y;
}
ll solve (ll c, ll d) {
	ll ans = 0;

	ll xmin = 1, xmax = 9, cshift = 10;
	while (xmin <= c + d) {
		ll l = max(xmin, c + 1);
		ll r = min(xmax, c + d);

		if (l <= r) {
			ll vl = c * cshift + l;
			ll vr = c * cshift + r;

			ans += (f(vr) - f(vl - 1));
		}

		xmin = xmin * 10;
		xmax = (xmax + 1) * 10 - 1;
		cshift *= 10;
	}

	return ans;
}

int main (void) {
	ll T;
	cin >> T;

	for (ll ti = 0; ti < T; ti++) {
		ll c, d;
		cin >> c >> d;

		ll ans = solve(c, d);
		cout << ans << "\n";
	}

	
	return 0;
}