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

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20303
Problem 303 「小さい桁を持つ倍数」 †

最初はそこそこ高速な計算だったのだが。
ｆ（9999）の場合だけ６４ビット整数型を越えてしまう問題に直面。
仕方なく遅い方法で実装し9999だけ特別に書きだしてPrologで計算。
計算時間１０分もかかる。
最初に割っておくにはどうすればよいのだろうか

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

struct E{
	__int64 mod,top,len;
	bool operator<(const E& e)const{
		if(len!=e.len)return len>e.len;
		if(top!=e.top)return top>e.top;
		return mod>e.mod;
	}
};

struct E2{
	std::list<int> li;
	bool operator<(const E2& e)const{
		return li<e.li;
	}
	void push_front(int n){
		li.push_front(n);
	}
	void print(){
		std::list<int>::iterator it;
		for(it=li.begin();it!=li.end();it++){
			printf("%d",(*it));
		}
		printf("\n");
	}
};

__int64 to_num(std::list<int> li){
	__int64 a=0;
	std::list<int>::iterator it;
	for(it=li.begin();it!=li.end();it++){
		a=a*10+(*it);
	}
	return a;
}
 
E2 calc(__int64 n){
	std::map<E,E2> memo;
	std::priority_queue<E> qu;
	
	__int64 a=1;
		
	E e1;
	e1.mod=0;
	e1.top=0;
	e1.len=0;
	qu.push(e1);
	E2 e22;
	
	memo[e1]=e22;
	int oldLen=0;
	while(qu.empty()==false){
		e1=qu.top();
		if(e1.len>oldLen){
			oldLen=e1.len;
			a=(a*10)%n;
		}
		qu.pop();
		if(e1.mod==0){
			if(e1.top==1||e1.top==2){
				return memo[e1];
			}
		}
		for(int i=0;i<=2;i++){
			E e2;
			e2.len=e1.len+1;
			e2.top=i;
			e2.mod=(e1.mod+a*i)%n;
			
			if(memo.find(e2)==memo.end()){
 				E2 e22=memo[e1];
				e22.push_front(i);
				memo[e2]=e22;
				qu.push(e2);
			}else{
				E2 e22=memo[e1];
				e22.push_front(i);
				if(e22<memo[e2])memo[e2]=e22;
			}
			
 				
			
		}
		
 	}
	return e22;
}

int main(){
	__int64 ans=0;
 	for(int i=1;i<=10000;i++){
		E2 e2=calc(i);
		if(e2.li.size()<=17){
			ans+=to_num(e2.li)/i;
		}else{
 			std::cout<<"\n"<<i<<" ";
			e2.print();
		}
 		if(i%400==0)std::cout<<i<<"\n";
	}
	std::cout<<ans<<"\n";
	
}