ARC174D Digit vs Square Root
题目大意
给定 \(N\)，求有多少个正整数 \(x(1\leq x\leq N)\) 满足：在十进制表示下，\(\lfloor x\rfloor\) 是 \(x\) 的前缀。
Solve
很难直接手推性质，考虑用如下程序打表：
#include<bits/stdc++.h>
#pragma GCC optimize(1,2,3,"Ofast","inline")
using namespace std;
#define int long long
inline bool check(int x,int y)
{
stack<int>a,b;
while(x)
a.push(x%10),x/=10;
while(y)
b.push(y%10),y/=10;
while(!a.empty())
{
if(a.top()!=b.top()) return 0;
a.pop();b.pop();
}
return 1;
}
signed main()
{
int res=0,j,lst;
for(int i=1;i<=1000000;i=-~i)
{
j=i;lst=res;
while(check(sqrt(j*1.0),j)) j=-~j,res=-~res;
if(j>i) printf("%lld~%lld: %lld~%lld\n",i,j-1,-~lst,res);
i=j;
}
return 0;
}
得到：
1~1: 1~1
80~80: 2~2
90~109: 3~22
9800~9800: 23~23
9900~10099: 24~223
998000~998000: 224~224
999000~1000999: 225~2224
我们不难可以发现这样的性质：
区间 \(\large[10^i-10^{\frac i 2},10^i+10^{\frac i 2}-1]\)（即 \(\large1,90\sim109,9900\sim10099\)）中的所有数 以及 \(\large10^i-2\times 10^{\frac i 2}\)（即 \(\large80,9800,998000\)）满足条件（\(\large i\) 均为偶数）。
仔细想一下，确实很对。
对于区间 \([10^i-10^{\frac i 2},10^i+10^{\frac i 2}-1](i\mod 2=0)\)，我们将他拆成 \([10^i-10^{\frac i 2},10^i-1]\) 和 \([10^i,10^i+10^{\frac i 2}-1]\) 来考虑：
-
对于 \([10^i-10^{\frac i 2},10^i-1]\)，即 \(9900\sim9999,999000\sim999999\)，显然他们开根向下取整都是 \(10^{\frac i 2}-1\)，即 \(99,999\)，而且它们的前 \(\frac i 2\) 位也是 \(10^{\frac i 2}-1\)。并且这些数的数位都是偶数，对于每个 \(i\) 有 \(10^{\frac i2}\) 个。
-
对于 \([10^i,10^i+10^{\frac i 2}-1]\)，即 \(10000\sim10099,1000000\sim1000999\)，它们开根向下取整都是 \(10^{\frac i 2}\)，即 \(100,1000\)，而它们的前 \(\frac i 2\) 位也是 \(10^{\frac i 2}\)。并且这些数的数位都是奇数，，对于每个 \(i\) 有 \(10^{\frac i2}\) 个。
对于 \(10^i-2\times 10^{\frac i 2}\)，即 \(80,9800,998000\)：
- \((10^{\frac i 2}-1)^2=10^i-2\times 10^{\lfloor\frac i 2\rfloor}+1\)，所以 \(\lfloor\sqrt{10^i-2\times 10^{\frac i 2}}\rfloor=10^{\frac i 2}-2\)，即 \(\lfloor\sqrt{80}\rfloor=8,\lfloor\sqrt{9800}\rfloor=98,\lfloor\sqrt{998000}\rfloor=998\)，显然 \(10^{\frac i 2}-2\) 是 \(10^i-2\times 10^{\frac i 2}\) 的前缀，而不是 \(10^i-2\times 10^{\frac i 2}-x\) 的前缀。这些数的数位都是偶数，，对于每个 \(i\) 有 \(1\) 个。
所以思路就很显然了：
-
首先处理出 \(1\sim 10^i-1\) 之间的所有符合条件的数的个数 \(sum_i\)。
-
对于每次询问，判断出 \(N\) 的位数 \(m\)，无论 \(m\) 是奇数还是偶数，答案 \(ans\) 都可以先加上 \(sum_{i-1}\)。
-
若 \(m\) 是偶数：如果 \(m\geq 10^m-2\times 10^{\frac m 2}\)，令 \(ans\) 加上 \(1\)；如果 \(N\geq 10^m-10^{\frac m 2}\)，令 \(ans\) 加上 \(N-(10^m-2\times 10^{\frac m 2})+1\)。
-
若 \(m\) 是奇数：令 \(ans\) 加上 \(\min(N,10^{m-1}+10^{\lfloor\frac m 2\rfloor}-1)-10^{m-1}\)。
Code
#include<bits/stdc++.h>
#pragma GCC optimize(1,2,3,"Ofast","inline")
using namespace std;
#define int long long
inline int read()
{
short f=1;
int x=0;
char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
inline int Get(int x)
{
int res=0;
while(x)
res=-~res,x/=10;
return res;
}
int t,n,sum[20],mi[20]={1},ans;
signed main()
{
for(int i=1;i<=18;i=-~i)
{
mi[i]=mi[i-1]*10;
sum[i]=sum[i-1]+mi[i/2];
if(i%2==0) sum[i]=-~sum[i];
}
// cout<<sum[3];
t=read();
while(t--)
{
n=read();
int res=Get(n);
// cout<<res<<endl;
ans=sum[res-1];
if(res%2==0)
{
// puts("into Case 1");
if(n>=mi[res]-2*mi[res/2]) ans=-~ans;
if(n>=mi[res]-mi[res/2]) ans+=n-(mi[res]-mi[res/2])+1;
}
else ans+=min(n,mi[res-1]+mi[res/2]-1)-mi[res-1]+1;
printf("%lld\n",ans);
}
return 0;
}