专栏文章

题解：AT_abc428_d [ABC428D] 183184

FFall_Dream
AT_abc428_d题解参与者 8已保存评论 9

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
9 条
当前快照
1 份
快照标识符
@minki3iy
此快照首次捕获于
2025/12/02 03:54
3 个月前
此快照最后确认于
2025/12/02 03:54
3 个月前
查看原文
在下文中，定义 len(x)\text{len}(x) 为 xx 的十进制位数，且 c,dc,d 表示题中 C,DC,D。
首先 f(c,c+x)f(c,c+x) 这个形式很难计数，所以考虑把它写成 c×(10l+1)+xc\times (10^l+1)+x。（ll 为 len(c+x)\text{len}(c+x)）
接下来考虑枚举 ll（因为 len(c+d)\text{len}(c+d) 可能大于 len(c)\text{len}(c)），根据题意易得 len(c+1)≤l≤len(c+d)\text{len}(c+1)\le l \le \text{len}(c+d)。
而因为 c+xc+x 是一个 ll 位数，能得出 10l−1≤c+x≤10l−110^{l-1}\le c+x \le10^l-1 且 1≤x≤d1\le x \le d。所以得 max⁡(1,10l−1−c)≤x≤min⁡(d,10l−c−1)\max(1,10^{l-1}-c) \le x \le \min(d,10^l-c-1)。我们得出第一个 xx 的范围。
接着整合题目中条件。需要 f(c,c+x)f(c,c+x) 为平方数，即 k2=x×(10l+1)+ck^2=x\times (10^l+1)+c 且 max⁡(1,10l−1−c)≤x≤min⁡(d,10l−c−1)\max(1,10^{l-1}-c) \le x \le \min(d,10^l-c-1)。移项一下 k2=c×(10l+1)+xk^2=c\times (10^l+1)+x 即得 x=k2−c×(10l+1)x=k^2-c\times (10^l+1)，再根据上文的条件并让上下界各加上 c×(10l+1)c\times (10^l+1) 可以得到求的是 max⁡(1,10l−1−c)+c×(10l+1)≤k2≤min⁡(d,10l−c−1)+c×(10l+1)\max(1,10^{l-1}-c)+c\times (10^l+1) \le k^2 \le \min(d,10^l-c-1)+c\times (10^l+1)。方便起见，将上界设为 rr，下界设为 ll。则可以通过差分思想得 ans=⌊r⌋−⌊l−1⌋ans=\left\lfloor\sqrt{r}\right\rfloor-\left\lfloor\sqrt{l-1}\right\rfloor。

代码：

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,d,c;
signed main(){
	cin>>T;
	while(T--){
		cin>>c>>d;
		int ans=0;
		int LL=log10(c+1)+1,RR=log10(c+d)+1;
		for(int i=LL;i<=RR;i++){
			__int128 mul=1;
			for(int j=1;j<=i;j++) mul*=10;
			__int128 lx=max(1ll,(int)(mul/10)-c),rx=min(d,(int)(mul-1-c));
			if(lx>rx) continue;
			__int128 l=c*mul+c+lx,r=c*mul+c+rx,x1=sqrtl(l-1),x2=sqrtl(r);
			ans+=x2-x1;
		}
		cout<<ans<<"\n";
	}
}
如果有公式打错，请私信我。否则求一个赞喵

评论

共 9 条评论，欢迎与作者交流。

正在加载评论...