プロジェクトオイラー問119

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20119
Problem 119 「数字べき乗和」 †
2桁以上の数の桁和のn乗が元の数と同じになるものがある。
小さいものから求め30個めの数を求めよ。

解法
桁和の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