Submission #70251401

---

Source Code Expand

#include<bits/stdc++.h>
#define LL long long
#define PII pair<int, int>
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
using namespace std;

inline void solve() {
	LL aa, bb, ans = 0; cin >> aa >> bb; __int128 c = (__int128)aa + 1, b = bb, a = aa; b = b - 1;
	int t = 0; LL vl = a;
	while (vl) {
		t++;
		vl /= 10;
	}
	vector<__int128> p(24); p[0] = 1;
	for (int i = 1; i <= 23; i++) p[i] = p[i - 1] * (__int128)10;
	while (b >= 0) {
		__int128 z = (__int128)a * p[t] + c, y = (__int128)a * p[t] + min(p[t] - 1, c + (__int128)b);
		__int128 l = sqrt(z + 0.5), r = sqrt(y + 0.5); 
		while (l * l < z) l++;
		while ((l - 1) * (l - 1) >= z) l--;
		while ((r + 1) * (r + 1) <= y) r++;
		while (r * r > y) r--;
		ans += max((__int128)0, r - l + 1);
//		cout << t << " " << (LL)z << " " << (LL)y << " " << (LL)l << " " << (LL)r << " " << (LL)(l * l) << " " << (LL)(r * r) << "\n";
		b -= p[t] - c;
		t++; c = p[t - 1];
	}
	cout << ans << "\n";
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int t = 1;
	cin >> t;
	while (t--) solve();
	return 0;
}

Submission Info

Judge Result