解法
桁和のn乗から優先順位付きキューで小さい順に探す。
桁和は小さい数なので問題ない。
#include <iostream>
#include <set>
#include <queue>
using namespace std;
struct E{
long long int num,b;
bool operator<(const E& e)const{
return num>e.num;
}
};
long long int ketawa(long long int n){
int re=0;
while(n>0){
re+=n%10;
n/=10;
}
return re;
}
int main() {
// your code goes here
std::priority_queue<E> pq;
std::set<int> commit;
E e1;
long long int limit=10;
int base=18;
for(int i=2;i<=18;i++){
e1.num=i*i;
e1.b=i;
pq.push(e1);
}
while(commit.size()<30){
e1=pq.top();
pq.pop();
while(e1.num>=limit){
limit*=10;
E e2;
for(int i=base+1;i<=base+9;i++){
e2.num=i*i;
e2.b=i;
pq.push(e2);
}
base+=9;
}
if((ketawa(e1.num)==e1.b)&&(commit.find(e1.num)==commit.end())){
commit.insert(e1.num);
cout<<e1.num<<"\n";
}
e1.num*=e1.b;
pq.push(e1);
}
return 0;
}
最終更新:2015年01月06日 15:33