AT_abc428_d [ABC428D] 183184

小清新思维题。

Solution

看到这个题一般都会想到去枚举完全平方数，然而

f(C,C+x)

最大可以达到

2\times 10^{18}

量级，不可行。

我们不妨换一个思路，注意到在钦定了

C+x

的位数

k

的前提下，

f(C,C+x)

能表示的是一个连续的范围。设

L,R

分别为这个范围的上界和下界，则有：

L=\max(C\times 10^k+10^{k-1},C\times 10^k+C+1)

R=\min[(C+1)\times 10^k-1,C\times 10^k+C+D]

L

需要和

C\times 10^k+10^{k-1}

取

\max

是因为

C+x

的位数必须为

k

，不能有前导零。

易证对于一段连续的区间

L,R

，若

l^2,r^2\ (l,r\ge0)

都在这段区间内，则对任意

l\le i\le r

，

i^2

都在这段区间内。令

l,r

分别为能使它的平方被区间包含的最小值/最大值，则有：

l=\left \lceil \sqrt{L} \right \rceil,r=\left \lfloor \sqrt{R} \right \rfloor

枚举

k

，累加

r-l+1

。

注意可能需要额外注意数据溢出的问题。

Code

CPP

#include<bits/stdc++.h>
#define int long long
#define ull unsigned int
using namespace std;
const int N = 200005;
ull t,c,d;
ull pw[N];
int p10(ull a)
{
	int ret = 0;
	while (a) ret++,a /= 10;
	return ret;
}
signed main()
{
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	pw[0] = 1;
	for (int i = 1; i <= 18; i++)
		pw[i] = pw[i-1]*10;
	cin >> t;
	while (t--)
	{
		cin >> c >> d;
		int ans = 0;
		for (int i = p10(c+1); i; i++)
		{
			ull l = c*pw[i]+max(pw[i-1],c+1),r = min((c+1)*pw[i]-1,c*pw[i]+c+d);
			if (l > r) break;
			ull beg = (int)sqrtl(l-1)+1,las = sqrtl(r);
			if (beg > las) continue;
			ans += las-beg+1;
			if (p10(r) >= 19) break;
		}
		cout << ans << '\n';
	}
	return 0;
}

题解：AT_abc428_d [ABC428D] 183184

文章操作

AT_abc428_d [ABC428D] 183184

Solution

Code

相关推荐

评论

题解：AT_abc428_d [ABC428D] 183184