Question portal
Main ideas
First of all, the scope of this question is\(10^9\), we can't directly\(1\)Loop to\(N\). It is not difficult to see that this question is to find whether the octal of square numbers is palindrome, and those that are not square numbers, for example\(2\)ah,\(3\)Yes, these are all unconsidered. We only need to loop from\(1\)arrive\(\left\lfloor\sqrt{n}\right\rfloor\)That's it. In this way, the time complexity is greatly reduced. There is nothing to say about the rest, see the code for details.
ACCode:
#include<iostream>
using namespace std;
string l0z8(int n){
string s;
while(n){
s=char(n%8+48)+s;
n/=8;
}
return s;
}
bool isHw(int n){
string s=l0z8(n);
int l=0,r=()-1;
while(l<=r){
if(s[l]!=s[r])return 0;
l++,r--;
}
return 1;
}
int main(){
int n;
cin>>n;
for(int i=1;i*i<=n;i++){
if(isHw(i*i)){
cout<<i*i<<' ';
}
}
return 0;
}
Code time complexity:\(\mathcal O\left(4\times\log_88\times\left\lfloor\sqrt{n}\right\rfloor\right)\)