给出长度为n的字符串s
通过排列组合问有多少种产生平方数的方式。
全排列时间复杂度O(13!)过大,不合适。
可以生成所有平方数放入数组,之后用这些数和输入的字符串位数字符数比较。
注意可以有前导0,所以长度不一致要补0.
#include
#include
#include
#define int long long
using namespace std;
signed main()
{
int n;string s;
cin>>n>>s;
vector<int>q;
for(int i=0;i<10000000;i++)
{
q.push_back(i*i);
}
int ans=0;
for(auto x:q){
int com[2][10]={0};
string t=to_string(x);//long long-->string
if(t.length()>s.length()) break;//平方数过大
com[0][0]=s.length()-t.length();//补足前导0
for(int i=0;i<t.length();i++){
com[0][t[i]-'0']++;
}
for(int i=0;i<s.length();i++){
com[1][s[i]-'0']++;
}
int f=1;
for(int i=0;i<=9;i++)
{
if(com[0][i]!=com[1][i]){
f=0;break;
}
}
if(f==1) ans++;
}
cout<<ans<<endl;
}