题目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

1. #coding:utf-8
   
2. i = int(1929394959697989990**0.5)
   
3. while i>=int(1020304050607080900**0.5):
   
4.     s = str(i*i)
   
5.     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'):
   
6.         print (i,i*i)
   
7.         break
   
8.     i -= 1

复制代码

输出：
1389019170 1929374254627488900

gunjang

1. from math import sqrt
   
2. import time
   
3. amax = 1929394959697989990
   
4. amin = 1020304050607080900
   
5. #print(int(sqrt(amin)), int(sqrt(amax))) #1010101010 1389026623 10^9
   
6. 
   
7. st = time.time()
   
8. 
   
9. waitinglist=[]
   
10. for a in range(10):
    
11.         if a*a % 10 == 0:
    
12.                 waitinglist.append(a)
    
13. maxDigit = len(str(int(sqrt(amin))))-1
    
14. if maxDigit%2 == 0: #9
    
15.         maxDigit -= 1
    
16. 
    
17. #n=a+b ==>n^2 = a^2+2ba+b^2
    
18. #low 3 digit
    
19. #let b = n%1000, a=(n//1000)*1000
    
20. #so a^2 's lower 3 digit is n^3 's lower 3 digit
    
21. for digit in range(3, maxDigit+1, 2):
    
22.         wl = []
    
23.         for x in waitinglist:
    
24.                 for b1 in range(0, 100):
    
25.                         b = b1*(10**(digit-2))+x
    
26.                         if (b*b % 10**digit)//10**(digit-1) == (10 - digit//2):
    
27.                                 wl.append(b)
    
28.         waitinglist = wl
    
29.         #print(digit,len(waitinglist)) #24000
    
30. 
    
31. def check(n):
    
32.         n = str(n)
    
33.         if (len(n)==19):
    
34.                 for i in range(5+1): #67890 have checked
    
35.                         if n[i*2]!=str(i+1):
    
36.                                 return False
    
37.         else:
    
38.                 return False
    
39.         return True
    
40. 
    
41. r = 0
    
42. for h in range(int(sqrt(amin))//10**maxDigit, int(sqrt(amax))// 10**maxDigit +1):
    
43.         for x in waitinglist:       
    
44.                 b = h* 10**9 + x
    
45.                 if check(b*b):
    
46.                         print(b, b*b)
    
47.                         r = b
    
48.                         break
    
49.         if r != 0:
    
50.                 break
    
51. #1389019170 1929374254627488900
    
52. 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

1. #include<iostream>
   
2. using namespace std;
   
3. 
   
4. 
   
5. int main() {
   
6.     unsigned long long i, n;
   
7.     unsigned char j;
   
8. 
   
9.     for (i = 101010103;;) {
   
10.         n = i * i;
    
11. 
    
12.         for (j = 9; j; j--) {
    
13.             if (n % 10 != j) {
    
14.                 goto next;
    
15.             }
    
16.             n /= 100;
    
17.         }
    
18. 
    
19.         cout << i * 10 << endl;
    
20.         return 0;
    
21. 
    
22.     next:
    
23.         i++;
    
24.     }
    
25. }

复制代码

debuggerzh

1389019170

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

1. #include<iostream>
   
2. #include<cmath>
   
3. using namespace std;
   
4. typedef long long ll;
   
5. 
   
6. const int lb = (int)sqrt((double)10203040506070809);
   
7. const int ub = (int)sqrt((double)19293949596979899);
   
8. 
   
9. bool judge(ll x){
   
10.   for (int i = 9;i >= 1;i--){
    
11.     if (x % 10 != i)  return false;
    
12.     x /= 100;
    
13.   }
    
14.   return true;
    
15. }
    
16. 
    
17. int main(){
    
18. 
    
19.   for (int i = lb;i <= ub;i++){
    
20.     ll t = (ll)i*i;
    
21.     int r = i % 10;
    
22.     if (r != 3 && r != 7) continue;
    
23. 
    
24.     if (judge(t)) {cout << i << 0 << endl; break;}
    
25.   }
    
26.   return 0;
    
27. }
    

复制代码