Submission #46553548

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
using vll = vector<vl>;
using Pll = pair<ll, ll>;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define Rep(i, j, n) for (ll i = (ll)(j); i <= (ll)(n); ++i)
#define all(v) v.begin(), v.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
const int MOD = 1e9 + 7;
const int mod = 998244353;
const ll INF = 2e15;
template <class T>
void print(const T& t) {
  cout << t << endl;
}
template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

/*
ll ti=clock();
cout<<("Execution Time: %.4lf sec", 1.0 * (clock() - ti) /
CLOCKS_PER_SEC)<<endl;
*/

int main(){
  ll n;
  cin>>n;
  string s;
  cin>>s;
  vl s_count(10,0);
  rep(i,sz(s)){
    s_count[s[i]-'0']++;
  }
  ll answer=0;
  for(ll i=0; i*i<=1e14;i++){
    ll x=i*i;
    string t=to_string(x);
    vl t_count(10,0);
    rep(j,sz(t)){
      t_count[t[j]-'0']++;
    }
    if(t_count[0]>s_count[0]){
      continue;
    }
    bool ok=true;
    Rep(j,1,9){
      if(t_count[j]!=s_count[j]){
        ok=false;
      }
    }
    if(ok){
      answer++;
    }
  }
  print(answer);
}

Submission Info

Judge Result