Note: It is highly recommended to read the hints before reading this editorial.

Hint 0 states, “You may feel the problem setting is somewhat unnatural. In such cases, how should you approach it initially?” One way to deal with situations where you’re unsure where to start is to conduct experiments.

Let’s enumerate some of the smallest \(N\)s that satisfy the conditions.

#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;
}

Experimental results (dotted lines indicate that all integers in that range appear in ascending order.)

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

Let’s compress consecutive integers and print the result over a wider range.

#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;
}

Experimental results 2

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

From here, it seems we can draw the following conclusion (let’s call it Fact A):

• Let \(K=10\). (This \(K\) represents the base)
• The set of integers that satisfy the conditions is a union of intervals of the following forms:
  • \([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)\)

This is indeed correct.

Assuming Fact A, the following solution works:

• Considering the constraint \(N \le 10^{18}\), the range of \(i\) to consider is \(1 \le i \le 9\).
• Also, the intervals mentioned in Fact A are all disjoint (have no common parts).
• Therefore, for a single \(N\), by determining the intersection between \([1,N]\) and the \(19\) intervals and summing up their lengths, the problem can be solved.

The time complexity per test case is \(O(1)\).

Sample implementation (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;
}

Now, let’s prove Fact A.

First, we fix the number of digits for \(x\) and \(y\). There are two patterns to consider:

• \(y\) has \(i+1\) digits, \(x\) has \(2i+1\) digits (Pattern 1)
• \(y\) has \(i\) digits, \(x\) has \(2i\) digits (Pattern 2)

For simplicity, we assume that cases where \(x\) and \(y\) have very small numbers of digits have been proved by exhaustive search.

On Pattern 1

Fix the prefix \(y=K^i + C\) \(( C \ge 0 )\). Then,

• From the square root condition, \(x\) should be within \([(K^i+C)^2, (K^i+C+1)^2-1]\)
• From the prefix condition, \(x\) should be within \([(K^i + C) K^i, (K^i + C + 1) K^i - 1]\)

Organizing this,

• The left end of the square root condition is \(K^{2i} + 2K^iC + C^2\).
• The right end of the prefix condition is \(K^{2i} + K^iC + K^i - 1\).

When \(C \ge 1\), comparing these,

\(K^{2i} + 2K^iC + C^2 > K^{2i} + K^iC + K^i - 1\)
\(\Leftrightarrow K^i(C-1) + C^2 + 1 > 0\)

This shows that no integers satisfy the conditions.

For the remaining case \(C=0\), we get an interval of integers that satisfy the conditions: \([K^{2i},K^{2i}+K^i-1]\) (S1).

On Pattern 2

Let us have a similar discussion as in Pattern 1.
Fix the prefix \(y=K^i - C\) \(( 0 < C < K^i )\). Then,

• From the square root condition, \(x\) should be within \([(K^i - C)^2, (K^i - C+1)^2-1]\)
• From the prefix condition, \(x\) should be within \([(K^i - C) K^i, (K^i - C + 1) K^i - 1]\)

Organizing this,

• The right end of the square root condition is \(K^{2i} - 2K^iC + 2K^i + C^2 - 2C\)
• The left end of the prefix condition is \(K^{2i} - K^iC\)

Comparing these,
\(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)\)
If this holds, that is, when \(2 < C < K^i\), the two intervals do not overlap.

Now, let’s process the cases \(C=1,2\).

For \(C=2\), we get an interval of integers that satisfy the conditions: \([K^{2i} - 2K^i, K^{2i} - 2K^i]\) (S2).

For \(C=1\), we get an interval of integers that satisfy the conditions: \([K^{2i} - K^i, K^{2i} - 1]\) (S3).

Putting (S1), (S2), and (S3) together proves Fact A. ■