|
#2
rjsp2013-12-12 09:34
懒得自己写算法，就尽量用了C++标准库中的算法，随手这么一写，抛砖引玉吧
 程序代码：#include <iostream> #include <algorithm> using namespace std; int main() { unsigned a[10]={ 0, 9, 8, 7, 6, 5, 4, 3, 2, 1 }; for( ; std::next_permutation(a+0,a+10); std::reverse(a+6,a+10) ) { unsigned n = a[0]*100000+a[1]*10000+a[2]*1000+a[3]*100+a[4]*10+a[5]*1; unsigned rest_flag = 1u<<a[6] | 1u<<a[7] | 1u<<a[8] | 1u<<a[9]; unsigned long long r = 1ull*n*n; for( ; r; r/=10 ) { if( !( 1u<<(r%10) & rest_flag ) ) break; } if( r == 0 ) cout << n << endl; } return 0; } |
小明正看着 203879 这个数字发呆。 原来，203879 * 203879 = 41566646641这有什么神奇呢？仔细观察，203879 是个6位数，并且它的每个数位上的数字都是不同的，并且它平方后的所有数位上都不出现组成它自身的数字。具有这样特点的6位数还有一个，请你找出它！
再归纳一下筛选要求：
1. 6位正整数
2. 每个数位上的数字不同
3. 其平方数的每个数位不含原数字的任何组成数位
这是我写的,,
程序代码：#include<iostream>
#include<string>
#include<sstream>
using namespace std;
bool judge(string ss){
for(int i=0;i!=ss.size();++i){
for(int j=i+1;j!=ss.size();++j){
if(ss[i]==ss[j])return 0;
}
}
return 1;
}
bool judge2(string s1,string s2){
for(int i=0;i!=s1.size();++i)
{for(int j=0;j!=s2.size();++j){
if(s1[i]==s2[j])
return false;}
}
return true;
}
bool doit(long long a)
{ ostringstream ostr;
ostr<<a;
string s;
istringstream istr(ostr.str());
istr>>s;
if(!judge(s)) return 0;
else{
long long a2=a*a;
ostringstream ostr1;
ostr1<<a2;
string s2;
istringstream istr1(ostr1.str());
istr1>>s2;
if(judge2(s,s2)&&a!=203879 )cout<<a;
}}
int main()
{ long long a=100000;
for(;a!=1000000;++a){
doit(a);
}
return 0;
}
#include<string>
#include<sstream>
using namespace std;
bool judge(string ss){
for(int i=0;i!=ss.size();++i){
for(int j=i+1;j!=ss.size();++j){
if(ss[i]==ss[j])return 0;
}
}
return 1;
}
bool judge2(string s1,string s2){
for(int i=0;i!=s1.size();++i)
{for(int j=0;j!=s2.size();++j){
if(s1[i]==s2[j])
return false;}
}
return true;
}
bool doit(long long a)
{ ostringstream ostr;
ostr<<a;
string s;
istringstream istr(ostr.str());
istr>>s;
if(!judge(s)) return 0;
else{
long long a2=a*a;
ostringstream ostr1;
ostr1<<a2;
string s2;
istringstream istr1(ostr1.str());
istr1>>s2;
if(judge2(s,s2)&&a!=203879 )cout<<a;
}}
int main()
{ long long a=100000;
for(;a!=1000000;++a){
doit(a);
}
return 0;
}
能输出正确答案,但是OJ判题时间超限;请教怎么可以缩短呢,