B*******1
发帖数: 2454 | 1 How to find a number of 10 digits (non repeated digits) which is a perfect
square? perfect square examples: 9 (3x3) 16 (4x4) 25(5x) etc. Ten digit
number example 1,234,567,890
我只想到用brute force,用0-9 permute 5位数字，然后求平方，看得出来的数字是不
是perfect square,有更加好的办法吗？
thanks |
x*******u
发帖数: 2074 | 2 binary search?
【在 B*******1 的大作中提到】
: How to find a number of 10 digits (non repeated digits) which is a perfect
: square? perfect square examples: 9 (3x3) 16 (4x4) 25(5x) etc. Ten digit
: number example 1,234,567,890
: 我只想到用brute force,用0-9 permute 5位数字，然后求平方，看得出来的数字是不
: 是perfect square,有更加好的办法吗？
: thanks
|
P*******1
发帖数: 1022 | 3 oh my god, it is so technical. you need to be a genius to work for google. |
c**********e
发帖数: 2007 | |
c*****m
发帖数: 315 | 5 binary search
MIN=1，MAX=1E6；
MID=(MIN+MAX)/2;
SMID=MID*MID;
IF(SMID>10 digit)
MAX=SMID;
ELSE IF(SMID<10 digit)
MIN=SMID;
ELSE
... |
c**********e
发帖数: 2007 | 6 Faint! All numbers from 31623 to 99999 have square with 10 digits.
But the question require no repeated digit. The number must be a permutation
of the 10 digits!
【在 c*****m 的大作中提到】
: binary search
: MIN=1，MAX=1E6；
: MID=(MIN+MAX)/2;
: SMID=MID*MID;
: IF(SMID>10 digit)
: MAX=SMID;
: ELSE IF(SMID<10 digit)
: MIN=SMID;
: ELSE
: ...
|
a****d
发帖数: 114 | 7 他要求10个digits不重复吧。只要 31623 <= X < 10^5, 那么 X^2一定是10 digits.
对每个X需要检测X^2是否所有digit不同。
【在 c*****m 的大作中提到】
: binary search
: MIN=1，MAX=1E6；
: MID=(MIN+MAX)/2;
: SMID=MID*MID;
: IF(SMID>10 digit)
: MAX=SMID;
: ELSE IF(SMID<10 digit)
: MIN=SMID;
: ELSE
: ...
|
c*****m
发帖数: 315 | 8 Sorry, not a careful person I am.
permutation
【在 c**********e 的大作中提到】
: Faint! All numbers from 31623 to 99999 have square with 10 digits.
: But the question require no repeated digit. The number must be a permutation
: of the 10 digits!
|
c**********e
发帖数: 2007 | 9 code:
#include
using namespace std;
int main() {
for(long n=31623;n<100000;n++) {
long nsquare=n*n;
int i,j, a[10];
for(i=0;i<10;i++) {
a[i]=nsquare % 10;
nsquare = nsquare/10;
}
for(i=0;i<10;i++) {
for(j=i+1;j<10;j++) {
if(a[i]>a[j]) {
int k=a[i]; a[i]=a[j]; a[j]=k;
}
}
}
i=0;
while(a[i]==i) i++;
if(i==10) cout << n << " " << nsquare << endl;
}
return 0;
} |
c**********e
发帖数: 2007 | 10 Answer:
32043 1026753849
32286 1042385796
33144 1098524736
35172 1237069584
35337 1248703569
35757 1278563049
35853 1285437609
37176 1382054976
37905 1436789025
38772 1503267984
39147 1532487609
39336 1547320896
40545 1643897025
42744 1827049536
43902 1927385604
44016 1937408256
45567 2076351489
45624 2081549376
... ... |
c**********e
发帖数: 2007 | 11 This code gives the complete answer. The previous one does not give a
complete answer due to restriction of long int (about 2-billion, 2^31-1).
#include
using namespace std;
int main() {
for(long n=31623;n<100000;n++) {
//long nsquare=n*n;
double nsquare=n*0.1*n;
long nsq=nsquare;
int i,j, a[10];
a[0]=(nsquare-nsq)*10;
for(i=1;i<10;i++) {
a[i]=nsq % 10;
nsq = nsq/10;
}
for(i=0;i<10;i++) {
for(j=i+1;j<10;j++) {
if(a[i]>a[j]) {
int k=a[i]; a[i]=a[j]; a[j]=k;
}
}
}
i=0;
while(a[i]==i) i++;
if(i==10) cout << n << " " << int(n*0.1*n) << (n % 10)*(n % 10) % 10 <<
endl;
}
return 0;
} |
c**********e
发帖数: 2007 | 12 Complete answer: 87 integers.
32043 1026753849
32286 1042385796
33144 1098524736
35172 1237069584
35337 1248703569
35757 1278563049
35853 1285437609
37176 1382054976
37905 1436789025
38772 1503267984
39147 1532487609
39336 1547320896
40545 1643897025
42744 1827049536
43902 1927385604
44016 1937408256
45567 2076351489
45624 2081549376
46587 2170348569
48852 2386517904
49314 2431870596
49353 2435718609
50706 2571098436
53976 2913408576
54918 3015986724
55446 3074258916
55524 3082914576
55581 3089247561
55626 3094251876
56532 3195867024
57321 3285697041
58413 3412078569
58455 3416987025
58554 3428570916
59403 3528716409
60984 3719048256
61575 3791480625
61866 3827401956
62679 3928657041
62961 3964087521
63051 3975428601
63129 3985270641
65634 4307821956
65637 4308215769
66105 4369871025
66276 4392508176
67677 4580176329
68763 4728350169
68781 4730825961
69513 4832057169
71433 5102673489
72621 5273809641
75759 5739426081
75923 5764301929
76047 5783146209
76182 5803697124
77346 5982403716
78072 6095237184
80361 6457890321
80445 6471398025
81222 6597013284
81945 6714983025
83919 7042398561
84648 7165283904
85353 7285134609
85743 7351862049
85803 7362154809
86073 7408561329
87639 7680594321
88623 7854036129
89079 7935068241
89145 7946831025
89355 7984316025
89523 8014367529
90144 8125940736
90153 8127563409
90198 8135679204
91248 8326197504
91605 8391476025
92214 8503421796
94695 8967143025
95154 9054283716
96702 9351276804
97779 9560732841
98055 9614783025
98802 9761835204
99066 9814072356 |
f*******t
发帖数: 7549 | 13 我觉得暴力法就可以了吧，看不出有什么特别好的算法。应该只是考coding熟练度的 |
