プロジェクトオイラー問516 - sinapusu2002 @ ウィキ

Problem 516 「5-スムーズトーシェント」 †

5-スムーズ数とは最大の素因数が5を超えないような数のことである.
5-スムーズ数はハミング数とも呼ばれる.
オイラーのトーシェント関数 φ(n) がハミング数となるような, Lを超えない数 n の値の和を S(L) としよう.
S(100)=3728.

S(10＾12) を求めよ. 回答は 2＾32 を法として答えよ.

夏の熱さでやられて簡単なことに気付かずループ。
時間がかかった。

解法
ファイ関数を求める公式から、条件を満たす数は２、３、５を素因数として持ち。
それより大きな素因数は一乗のものしか持たない。
そして大きな素因数は（２，３，５を素因数としてもつ数に１を足した）素数以外条件を満たせない。
これは公式から明らか。
後は１を忘れずに足すだけ。
コードがコンパクトになった。
こういう簡単な問題だけならいいんだけどね。
５００番台は難しい問題のほうが多いな。

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

//S(10000)=9586559

const __int64 LIMIT=pow(10,12);
const __int64 MOD=pow(2,32);
__int64 as[3]={2,3,5}; 

unsigned __int64 ans=0;
std::set<unsigned __int64> memo,memo2;


bool is_prime(__int64 n){
	for(__int64 i=2;i*i<=n;i+=1+(i&1)){
		if(n%i==0)return false;
	}
	return true;
}

void search(__int64 n,int p){
	if(n>LIMIT)return;
	if(n+1<=LIMIT){
		if(is_prime(n+1)&&(n+1>5)){
			memo2.insert(n+1);
		}
	}
	memo.insert(n);
	search(n*as[p],p);
 	if(p<2){
		search(n,p+1);
	}
}

void search2(unsigned __int64 a,std::set<unsigned __int64>::iterator& it,bool addOK){
 	ans+=(a*addOK);
	ans%=MOD;
	std::set<unsigned __int64>::iterator it2;
	if(it==memo2.end())return ;
	long double b=(*it);
	long double c=a;
	if(c*b>LIMIT)return ;
	it2=it;
 	it2++;
	search2(a*(unsigned __int64)b,it2,true);
	search2(a,it2,false);	
}


int main(){
	search(1,0);
	std::set<unsigned __int64>::iterator it,it2;
	for(it=memo.begin();it!=memo.end();it++){
		it2=memo2.begin();
		std::cout<<"\na="<<(*it)<<"\n";
 		search2((*it),it2,true);
	}
	std::cout<<ans<<"\n";
}