プロジェクトオイラー問１１９ - c21coterie @ ウィキ

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20119

Problem 119 「数字和のべき乗」 †

512 という数は興味深い数である. というのも, 各桁の和を何乗かしたものに等しくなっているからである: 5 + 1 + 2 = 8, 8＾3 = 512 である. この特性を持つ他の数は例えば 614656 = 28＾4 である.

この数列の第 n 項を an と定義し, また 2 桁以上であるとしよう.

a2 = 512, a10 = 614656 となる.

a30 を求めよ.

解法
各桁の和はまあ大きく見積もっても200くらいです。
その1＾ｎから200＾ｎまでの乗数を小さいほうから求めます。
ｍ＾ｎの各桁の和でm^nをあまりなく割り続けて1に到達したらその数は条件を満たす数です。
割り切れなければその数は駄目ということです。
この発想で計算量はＢｉｇＯ（1559）
まあまあですね。

#include<stdio.h>
#include<queue>
#include<iostream>

struct powNum{
	__int64 base,n;
	bool operator<(const powNum& pn)const{
		return n>pn.n;
	}
	__int64 ketaSum(){
		__int64 result=0;
		__int64 n1=n;
		while(n1>0){
			result +=n1%10;
			n1/=10;
		}
		return result;
	}
};

bool ok_pow(__int64 n,__int64 div){
 	if(div<2)return false;
 	if(n==1)return true;
 	if(n%div>0)return false;
 	return ok_pow(n/div,div);
}
 
int main(){
	int count=0,stop=0;
	powNum pn,pn1;
	pn.base=2;
	pn.n=2;
	std::priority_queue<powNum> pq;
	pq.push(pn);
	__int64 min=0;
	int bigO=0;
	while(pq.empty()==false){
		pn=pq.top();
		pq.pop();
		bigO++;
 		if(pn.n>=10){
			__int64 kSum= pn.ketaSum();
			
			if(min<pn.n && ok_pow(pn.n,kSum)){
				min=pn.n;
				count++;
				std::cout<<"\n<"<<count<<" "<<pn.n<<">\n";
				if(count==30)break;
			}
		}
		if(pn.n>200&&pn.n==pn.base)continue;
		if(pn.n==pn.base){
 			pn1.n=pn.n+1;
			pn1.base=pn.base+1;
			pq.push(pn1);
		}
		pn.n*=pn.base;
		pq.push(pn);
	}
	std::cout<<"計算量"<<bigO<<"\n";
}