本文最后更新于 600 天前,其中的信息可能已经有所发展或是发生改变。
思想:
- 贪心,枚举。
- 对于满足条件最大的数,我们枚举其因子 $i$:
- 保证 $i$ 从 $\sqrt{n}$ 开始递减枚举;
- 得到 $st = i \times i$,判断 $st$ 是否可由删除 $n$ 的某些位得到。
- 若首次找到符合条件的数,即为所求;
- 否则,直到 $i = 1$ 还未找到满足条件的数,说明不存在。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
string s;
bool check(LL x){
string st = to_string(x); // 得到 st = i * i
int idx = 0; // 遍历 st 的下标
for(int i = 0; i < s.size(); i ++){
if(idx < st.size() && st[idx] == s[i]) idx ++; // st[idx] == s[i] 说明当前位照应,则 idx 后移
} // 否则说明应当删除当前位
if(idx == st.size()) return 1; // 若 idx 遍历完了 st , 说明可以经过操作得到 st
return 0;
}
void solve(){
LL n; cin >> n;
s = to_string(n); // 将 n 转换为 strintg 类型,便于后续枚举位来比较
for(LL i = sqrtl(n); i >= 1; i --){ // i 从 sqrtl(n) 开始递减枚举
if(check(i * i)){ // 判断是否满足
string st = to_string(i * i); // 得到 st = i * i
cout << s.size() - st.size() << endl; // 输出操作次数,即为长度的差值
return ;
}
}
cout << -1 << endl;
}
int main(){
int _; cin >> _;
while(_ --) solve();
return 0;
}