题目206：隐藏的平方数

欧拉计划

Concealed Square

Find the unique positive integer whose square has the form 1_2_3_4_5_6_7_8_9_0,
where each “_” is a single digit.

题目：

找出唯一一个符合如下条件的数字：它的平方是具有 1_2_3_4_5_6_7_8_9_0 形式的数。

每个 _ 都代表了单个数字。

jerryxjr1220

#coding:utf-8
i = int(1929394959697989990**0.5)
while i>=int(1020304050607080900**0.5):
    s = str(i*i)
    if (s[0],s[2],s[4],s[6],s[8],s[10],s[12],s[14],s[16],s[18]) == ('1','2','3','4','5','6','7','8','9','0'):
        print (i,i*i)
        break
    i -= 1

输出：
1389019170 1929374254627488900

gunjang

from math import sqrt
import time
amax = 1929394959697989990
amin = 1020304050607080900
#print(int(sqrt(amin)), int(sqrt(amax))) #1010101010 1389026623 10^9

st = time.time()

waitinglist=[]
for a in range(10):
        if a*a % 10 == 0:
                waitinglist.append(a)
maxDigit = len(str(int(sqrt(amin))))-1
if maxDigit%2 == 0: #9
        maxDigit -= 1

#n=a+b ==>n^2 = a^2+2ba+b^2
#low 3 digit 
#let b = n%1000, a=(n//1000)*1000
#so a^2 's lower 3 digit is n^3 's lower 3 digit
for digit in range(3, maxDigit+1, 2):
        wl = []
        for x in waitinglist:
                for b1 in range(0, 100):
                        b = b1*(10**(digit-2))+x
                        if (b*b % 10**digit)//10**(digit-1) == (10 - digit//2):
                                wl.append(b)
        waitinglist = wl
        #print(digit,len(waitinglist)) #24000

def check(n):
        n = str(n)
        if (len(n)==19):
                for i in range(5+1): #67890 have checked
                        if n[i*2]!=str(i+1):
                                return False
        else:
                return False
        return True

r = 0
for h in range(int(sqrt(amin))//10**maxDigit, int(sqrt(amax))// 10**maxDigit +1):
        for x in waitinglist:        
                b = h* 10**9 + x
                if check(b*b):
                        print(b, b*b)
                        r = b
                        break
        if r != 0:
                break
#1389019170 1929374254627488900
print(time.time()-st) #0.75s

1389019170 1929374254627488900

guosl

这个题目可以先做一些数学上的简单分析：平方后的数最后一个数字是0，那么原数的最后一位一定是0；所以平方后的数最后二位一定都是0；去掉这两个零后平方后的数最后一位是9，故原数的最后一位一定是3或7。然后开方10203040506070809和19293949596979899得10101010和13890266。而最后一个数只能是3或7。所以搜索范围为：1010101030到1389026670之间。如果在加上平行编程可以把时间控制在1秒以下。

永恒的蓝色梦想

C++ 680ms

#include<iostream>
using namespace std;


int main() {
    unsigned long long i, n;
    unsigned char j;

    for (i = 101010103;;) {
        n = i * i;

        for (j = 9; j; j--) {
            if (n % 10 != j) {
                goto next;
            }
            n /= 100;
        }

        cout << i * 10 << endl;
        return 0;

    next:
        i++;
    }
}

debuggerzh

1389019170

Process returned 0 (0x0)   execution time : 0.555 s
Press any key to continue.
4#的c++实现~

#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;

const int lb = (int)sqrt((double)10203040506070809);
const int ub = (int)sqrt((double)19293949596979899);

bool judge(ll x){
  for (int i = 9;i >= 1;i--){
    if (x % 10 != i)  return false;
    x /= 100;
  }
  return true;
}

int main(){

  for (int i = lb;i <= ub;i++){
    ll t = (ll)i*i;
    int r = i % 10;
    if (r != 3 && r != 7) continue;

    if (judge(t)) {cout << i << 0 << endl; break;}
  }
  return 0;
}