注: この問題は、解説を読む前にヒントを読むことを強く推奨します。

Hint 0 に、「問題設定が多少不自然に感じるかもしれません。このような場合、初手をどう打つべきでしょうか?」とあります。
初手をどう打つべきか分からない状況への対処は、やはり 実験を行う ことでしょう。

条件を満たす \(N\) を、小さいほうからいくつか列挙してみましょう。

#include<bits/stdc++.h>

using namespace std;

long long sq(long long x){
  long long l=0,r=2e9;
  while(l<=r){
    long long te=(l+r)/2;
    if(te*te <= x){l=te+1;}
    else{r=te-1;}
  }
  return r;
}

int main(){
  for(long long x=1;x<=11111;x++){
    long long y=sq(x);
    string s=to_string(x);
    string t=to_string(y);
    bool ok=true;
    for(int i=0;i<t.size();i++){
      if(s[i]!=t[i]){ok=false;}
    }
    if(ok){cout << x << "\n";}
  }
  return 0;
}

実験結果 (点線部は、その間にある整数が小さい方から順に全て出現している。)

1
80
90
91
...
108
109
9800
9900
9901
...
10099

連続した整数を圧縮して、もう少し広い範囲で出力してみましょう。

#include<bits/stdc++.h>

using namespace std;

long long sq(long long x){
  long long l=0,r=2e9;
  while(l<=r){
    long long te=(l+r)/2;
    if(te*te <= x){l=te+1;}
    else{r=te-1;}
  }
  return r;
}

int main(){
  bool pre=false;
  for(long long x=1;x<=111111111;x++){
    long long y=sq(x);
    string s=to_string(x);
    string t=to_string(y);
    bool ok=true;
    for(int i=0;i<t.size();i++){
      if(s[i]!=t[i]){ok=false;}
    }
    if(pre!=ok){
      if(ok){
        cout << "[ " << x << " , ";
      }
      else{
        cout << x-1 << " ]\n";
      }
    }
    pre=ok;
  }
  return 0;
}

実験結果2

[ 1 , 1 ]
[ 80 , 80 ]
[ 90 , 109 ]
[ 9800 , 9800 ]
[ 9900 , 10099 ]
[ 998000 , 998000 ]
[ 999000 , 1000999 ]
[ 99980000 , 99980000 ]
[ 99990000 , 100009999 ]

以下の結論らしきものが見えてきたと思います。(事実 A とします)

• \(K=10\) とする。 (この \(K\) は \(K\) 進数を表現しています)
• 条件を満たす整数の集合は、次の形の区間の和集合である。
  • \([1,1]\)
  • \([K^{2i}-K^i, K^{2i}+K^i-1]\) \((i \ge 1)\)
  • \([K^{2i}-2K^i, K^{2i}-2K^i]\) \((i \ge 1)\)

実際にこれは正しいです。

事実 A を認めると、以下の解法が成立します。

• \(N \le 10^{18}\) の制約下で考えるべき \(i\) の範囲は \(1 \le i \le 9\) である。
• また、事実 A で登場した区間は全て disjoint(共通部分を持たない) である。
• なので、ひとつの \(N\) に対して、 \([1,N]\) と \(19\) 個の区間との共通部分を判定し、それらの長さを足し合わせることで求解できる。

テストケースあたりの時間計算量は \(O(1)\) となります。

実装例(C++):

#include<bits/stdc++.h>

using namespace std;
using pl=pair<long long,long long>;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  vector<pl> segs={{1,1}};
  long long k2=1,k1=1;
  for(long long i=1;i<=9;i++){
    k2*=100; k1*=10;
    segs.push_back({k2-2*k1,k2-2*k1});
    segs.push_back({k2-k1,k2+k1-1});
  }
  // for(auto &nx : segs){
  //   cout << nx.first << " " << nx.second << "\n";
  // }

  int t;
  cin >> t;
  while(t>0){
    t--;
    long long n;
    cin >> n;
    long long res=0;
    for(auto &nx : segs){
      long long l=nx.first;
      long long r=min(n,nx.second);
      if(l<=r){res+=(r-l+1);}
    }
    cout << res << "\n";
  }
  return 0;
}

ここからは事実 A を証明していきましょう。

最初に \(x,y\) の桁数を決め打ちます。考えるべきは以下の \(2\) 通りです。

• \(y\) が \(i+1\) 桁、 \(x\) が \(2i+1\) 桁 (パターン1)
• \(y\) が \(i\) 桁、 \(x\) が \(2i\) 桁 (パターン2)

単純のため、 \(x,y\) の桁数が非常に小さい場合は全探索によって証明できたものとします。

パターン1について

接頭辞 \(y=K^i + C\) \(( C \ge 0 ) \) と決め打ちます。このとき、

• 平方根の条件から、 \(x\) は \([(K^i+C)^2, (K^i+C+1)^2-1]\) の中にあるべき
• 接頭辞の条件から、 \(x\) は \([(K^i + C) K^i, (K^i + C + 1) K^i - 1]\) の中にあるべき

これを整理すると

• 平方根の条件の左端は \(K^{2i} + 2K^iC + C^2\)
• 接頭辞の条件の右端は \(K^{2i} + K^iC + K^i - 1\)

となります。 \(C \ge 1\) であるときはこれらを大小比較して

\(K^{2i} + 2K^iC + C^2 > K^{2i} + K^iC + K^i - 1\)
\(\Leftrightarrow K^i(C-1) + C^2 + 1 > 0\)
から条件を満たす整数は存在しないことが示されます。

残った \(C=0\) については、 \([K^{2i},K^{2i}+K^i-1]\) という条件を満たす整数の区間を得ます。(S1)

パターン2について

パターン \(1\) と同様の議論を行います。
接頭辞 \(y=K^i - C\) \(( 0 < C < K^i ) \) と決め打ちます。このとき、

• 平方根の条件から、 \(x\) は \([(K^i - C)^2, (K^i - C+1)^2-1]\) の中にあるべき
• 接頭辞の条件から、 \(x\) は \([(K^i - C) K^i, (K^i - C + 1) K^i - 1]\) の中にあるべき

これを整理すると

• 平方根の条件の右端は \(K^{2i} - 2K^iC + 2K^i + C^2 - 2C\)
• 接頭辞の条件の左端は \(K^{2i} - K^iC\)

これらを大小比較します。
\(K^{2i} - 2K^iC + 2K^i + C^2 - 2C < K^{2i} - K^iC\)
\(\Leftrightarrow C^2 - 2C < K^iC - 2K^i\)
\(\Leftrightarrow C(C-2) < K^i (C-2)\)
が成り立つ、すなわち \(2 < C < K^i\) であるときはふたつの区間に重複はありません。

あとは \(C=1,2\) の場合を処理しましょう。

\(C=2\) の場合、 \([K^{2i} - 2K^i, K^{2i} - 2K^i]\) という条件を満たす整数の区間を得ます。(S2)

\(C=1\) の場合、 \([K^{2i} - K^i, K^{2i} - 1]\) という条件を満たす整数の区間を得ます。(S3)

(S1)(S2)(S3) を網羅することにより、事実 A が証明されました。■