排它平方数

ivor

小明正看着 203879 这个数字发呆。

    原来，203879 * 203879 = 41566646641

    这有什么神奇呢？仔细观察，203879 是个6位数，并且它的每个数位上的数字都是不同的，并且它平方后的所有数位上都不出现组成它自身的数字。

    具有这样特点的6位数还有一个，请你找出它！

    再归纳一下筛选要求：
    1. 6位正整数
    2. 每个数位上的数字不同
    3. 其平方数的每个数位不含原数字的任何组成数位

答案是一个6位的正整数。

1. $start=[System.DateTime]::Now
   
2. for($a=100001;$a -le 999999;$a++){
   
3. if ((([char[]]($a).ToString()| group).Length -eq 6) -and (([char[]][math]::Pow($a,2).ToString()).Where({$a.ToString().contains($_)}).Count -eq 0)){
   
4.     Write-Host $a
   
5. }
   
6. }
   
7. ([System.DateTime]::Now - $start).TotalSeconds

复制代码

1. 
   
2. 203879
   
3. 639172
   
4. "耗时:"100.269806

复制代码

转载：https://blog.csdn.net/u012027907/article/details/14157077

bailong360

1. 
   
2. from itertools import permutations
   
3. 
   
4. for digits in permutations((str(x) for x in range(10)), 6):
   
5.     if digits[0] == '0':
   
6.         continue
   
7.     num = int("".join(digits))
   
8.     square = num ** 2
   
9.     if not set(str(square)) & set(digits):
   
10.         print(num)
    

复制代码

结果

1. 
   
2. 203879
   
3. 639172
   
4. CPU times: user 304 ms, sys: 0 ns, total: 304 ms
   
5. Wall time: 304 ms
   

复制代码

选 Python 主要是标准库里有 permutations, 省事儿 (

523066680

1. use Time::HiRes qw/time/;
   
2. use Algorithm::Permute;
   
3. 
   
4. my $ta = time();
   
5. my $iter = Algorithm::Permute->new ( [0..9], 6 );
   
6. my (@digits, @res);
   
7. my ($num, $unique);
   
8. 
   
9. # 尾数 0 1 5 6 相乘都产生与本身相同尾数的值
   
10. my @repeat = map { ($_ * $_) =~ $_ ? 1 : 0  } (0 .. 9);
    
11. 
    
12. while ( @res = $iter->next )
    
13. {
    
14.     next if $res[0] == 0;
    
15.     next if $repeat[ $res[-1] ];
    
16. 
    
17.     $num = join("", @res);
    
18.     @digits = (0)x10;
    
19.     $unique = 1;
    
20.     grep { $digits[$_] = 1 } @res;
    
21.     for (split("", $num * $num )) {
    
22.         $unique = 0, last if $digits[$_]
    
23.     }
    
24.     printf "%d\n", $num if $unique;
    
25. }
    
26. 
    
27. printf "time usage: %.2fs\n", time()-$ta;

复制代码

1. 639172
   
2. 203879
   
3. time usage: 0.40s

复制代码

强行优化，0 1 5 6 平方后末位与自身相同
my @repeat = map { ($_ * $_) =~ $_ ? 1 : 0  } (0 .. 9);

523066680

提速，在递归排列的每一层都做重复数的排查。
细节，例如当前累积到3位数，133*133 = 17689，那么只判断 689 是否与 133重合，而不考虑 17，因为 17 可能受到高位数的影响而变化。

1. use Time::HiRes qw/time/;
   
2. my $ta = time();
   
3. our $maxlen = 6;
   
4. permute([], [0..9], 0);
   
5. 
   
6. printf "time usage: %.2fs\n", time() - $ta;
   
7. 
   
8. sub permute
   
9. {
   
10.     my ($a, $b, $lv) = @_;
    
11. 
    
12.     return if $lv > $maxlen;
    
13.     if ( $lv > 0 and $a->[0] != 0 )
    
14.     {
    
15.         my $n = join("", @$a);
    
16.         my $mp = $n*$n;
    
17.         $mp = substr($mp, -$lv) if ($lv < $maxlen);
    
18.         for ( 0 .. $#$a ) { return if $mp =~ $a->[$_] }
    
19.         if ($lv == $maxlen)
    
20.         {
    
21.             printf "%d %d\n",  $n, $mp;
    
22.             return;
    
23.         }
    
24.     }
    
25. 
    
26.     for ( 0 .. $#{$b} ) {
    
27.         permute( [ $b->[$_], @$a ] , [@{$b}[0..$_-1, $_+1..$#$b]], $lv+1);
    
28.     }
    
29. }
    

复制代码

639172 408540845584
203879 41566646641
time usage: 0.05s

liujingcheng

剪枝：
1：个位为0,1,5,6可以直接跳过。
2：只要发现某一位重复，跳过
附一下代码：

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. int a[10],flag;
   
4. int main()
   
5. {
   
6.         for(long long i=100000;i<=999999;++i)
   
7.         {
   
8.                 for(int j=0;j<=9;++j)a[j]=0;
   
9.                 flag=0;
   
10.                 if(i%10==0||i%10==1||i%10==5||i%10==6)continue;
    
11.                 long long m=i*i;
    
12.                 a[i%10]=1;
    
13.                 if(a[i/10%10]==1)continue;
    
14.                 a[i/10%10]=1;
    
15.                 if(a[i/100%10]==1)continue;
    
16.                 a[i/100%10]=1;
    
17.                 if(a[i/1000%10]==1)continue;
    
18.                 a[i/1000%10]=1;
    
19.                 if(a[i/10000%10]==1)continue;
    
20.                 a[i/10000%10]=1;
    
21.                 if(a[i/100000%10]==1)continue;
    
22.                 a[i/100000%10]=1;
    
23.                 while(m>0)
    
24.                 {
    
25.                         if(a[m%10]==1)
    
26.                         {
    
27.                                 flag=1;
    
28.                                 break;
    
29.                         }
    
30.                         m/=10;
    
31.                 }
    
32.                 if(flag)continue;
    
33.                 for(int j=0;j<=9;++j)
    
34.                 {
    
35.                         if(a[j]>1)continue;
    
36.                 }
    
37.                 cout<<i<<"\n";
    
38.                 flag=0;
    
39.         }
    
40. }

复制代码

耗时：0.1638s
是不是很快？C++就是快。
STL**好，退C转C++保平安。