剪枝:
1:个位为0,1,5,6可以直接跳过。
2:只要发现某一位重复,跳过
附一下代码:- #include<bits/stdc++.h>
- using namespace std;
- int a[10],flag;
- int main()
- {
- for(long long i=100000;i<=999999;++i)
- {
- for(int j=0;j<=9;++j)a[j]=0;
- flag=0;
- if(i%10==0||i%10==1||i%10==5||i%10==6)continue;
- long long m=i*i;
- a[i%10]=1;
- if(a[i/10%10]==1)continue;
- a[i/10%10]=1;
- if(a[i/100%10]==1)continue;
- a[i/100%10]=1;
- if(a[i/1000%10]==1)continue;
- a[i/1000%10]=1;
- if(a[i/10000%10]==1)continue;
- a[i/10000%10]=1;
- if(a[i/100000%10]==1)continue;
- a[i/100000%10]=1;
- while(m>0)
- {
- if(a[m%10]==1)
- {
- flag=1;
- break;
- }
- m/=10;
- }
- if(flag)continue;
- for(int j=0;j<=9;++j)
- {
- if(a[j]>1)continue;
- }
- cout<<i<<"\n";
- flag=0;
- }
- }
复制代码 耗时:0.1638s
是不是很快?C++就是快。
STL**好,退C转C++保平安。 |