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

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2029
Problem 29 「個別のべき乗」 †
2<=a<=100,2<=b<=100,a^bで作ることのできる数の個数をこたえる問題。

簡単なので
2<=a<=100000,2<=b<=100000
計算時間 0.43sec
答え 9981236306
と挑戦してみた。
答えあってるかな。

a0を素因数分解した時、
素因数2の数を1次元めに
素因数3の数を2次元目に
、、、
とベクトルでaを表すと、aのある数a0とa1はa0^nとa1^mのベクトルが重なるかどうか、つまりベクトルの定数倍の問題に帰着することを利用して解。


#include<stdio.h>
#include<map>
#include<set>
#include<iostream>

const int LIMIT=100000;
int main(){
	int bads[LIMIT+1]={0};
	std::map<int,__int64> memo;
	std::set<int> all;

	for(int i=1,p=1;p<=LIMIT*2;p*=2,i++){
		for(int j=2;j<=LIMIT;j++){
 			all.insert(i*j);
		}
		memo[i]=all.size();
		std::cout<<"("<<i<<" "<<all.size()<<"\n";
	}


	__int64 ans=0;
	for(int i=2;i<=LIMIT;i++){
		if(bads[i]==0){
			__int64 p=i;
 			int count=0;
			while(p<=LIMIT){
				bads[(int)p]=1;
				count++;
				p*=i;
			}
			ans+=memo[count];
		}
	}
	std::cout<<"ans="<<ans<<"\n";
}
最終更新:2014年12月01日 08:09