AtCoder Beginner Contest 428 D - 183184

1.问题解析

f(x,y)= x + y这里的x+y是x和y的字符串拼接形成的对应的数字。
输入C和D找到所有x的个数：

1. 1 <= x <= D
2. f(C, C + x)是完全平方数

2.解决思路

假设C+x的位数有i位，则有

\[\begin{aligned}N^2 &= C \times 10^i + (C + x)\\&=C(10^i + 1) + x \end{aligned}（拼接后的数） \]

由于C+x的位数是i
=> C+x的取值范围为$ [10^{i-1}, 10^i - 1] $

=> 则x的取值范围是$ [10^{i-1}-C, 10^i - 1-C] $

设

\[L=max(1, 10^{i-1}-C),R=min(D,10^i-1-C) \]

所以我们的结果等效与：求$ [C (10^i+1) + L, C(10^i+1) + R] $中的完全平方数的的个数
=> 即求开方后这个里面整数的个数
我们遍历每一个i,然后按照思路维护结果值。

3.代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll> pow10(19, 1);void solve()
{ll c, d, ans = 0;cin >> c >> d;ll l = to_string(c+1).length(), r = to_string(c + d).length();for(ll i = l; i <= r; i++){ll L= max<ll>(1, pow10[i-1]-c), R = min<ll>(d, pow10[i] - 1-c);ll n2l = c * (pow10[i] + 1) + L, n2r = c * (pow10[i] + 1) + R;ll nl = ceill(sqrtl(n2l)), nr = floorl(sqrtl(n2r));ans += max<ll>(0, nr - nl + 1);//加上区间的宽度，也就是整数的个数}cout << ans << endl;
}
int main()
{//预处理pow10for(int i = 1; i <= 18; i++)pow10[i] = pow10[i-1] * 10;std::ios::sync_with_stdio(0);std::cin.tie(0);int t;cin >> t;while(t--){solve();}
}

学习来源：https://zhuanlan.zhihu.com/p/1963011889832395059