题解 | #小红的完全平方数构造# 二分简单做法

假设当前数字是114514，我们得到的答案必定是114514abcd

• 枚举扩展位数，由于答案说明在18位以内，故扩展位数最多枚举18次

• 获取扩展后的，例如我们扩展了2位，应该得到11451400

• 寻找第一个大于等于11451400的完全平方数，在二分的时候二分的是 中的，由于最大答案不会超过18位，因为直接枚举到 即可

• 当这个数减去11451400的结果小于100时（即恰好可以填完00，他前面几个数和没扩展的一样），说明可以构成答案，否则就继续扩展。

总时间复杂度，事实上这个常数非常小，跑了不到。

#include <iostream>
#include <math.h>
using namespace std;
typedef long long ll;
ll pre[20];

int _log10(ll x){
    int ws=0;
    while(x){
        ws++;
        x/=10;
    }
    return ws;
}
void solve(){
    ll x;
    cin>>x;
    int ws=_log10(x);
    for(int i=1;i<=18;i++){ //枚举扩展的位数
        if(ws-1+i>18)break; //如果位数扩展超出了18位就不枚举了
        ll y=x*pre[i];
        ll l=1,r=1e9;
        while(l<r){
            ll mid=(l+r)>>1;
            if(mid*mid >=y)r=mid;
            else l=mid+1;
        }
        if(l*l - y < pre[i]){//例如12345 -12300=45
            cout<<l*l<<"\n";
            break;
        }
    }
    return;
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int T=1;
    cin>>T;
    pre[0]=1;
    for(int i=1;i<=18;i++)pre[i]=pre[i-1]*10;
    while(T--)solve();
    return 0;
}