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

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

Problem 132 「巨大なレピュニットの因数」 †
1のみからなる数をレピュニットという. R(k) を長さ k のレピュニットとする.

例えば, R(10) = 1111111111 = 11×41×271×9091 となり, 素因数の和は9414となる.

R(10^9) の最初の40個の素因数の和を求めよ.

modPowで簡単に解けます。
計算時間3秒

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

const int LIMIT=10000*10000*10;

bool isP(int n){
	for(int i=2;i*i<=n;i++){
		if(n%i==0)return false;
	}
	return true;
}


int main(){
	std::set<int> ds;
	for(int i=1;i*i<=LIMIT;i++){
		if(LIMIT%i==0){
			ds.insert(i);
			ds.insert(LIMIT/i);
		}
	}
	int p=3;
	int c=0;
	int ans=0;
	while(c<40){
		if(isP(p)==false){
			p+=2;
			continue;
		}
		bool hit=false;
		for(std::set<int>::iterator it=ds.begin();it!=ds.end();it++){
			__int64 n=(*it);
			__int64 n1=0,m1=1;
			__int64 n2=1,m2=10;
			while(n>0){
				if(n%2==1){
					n1=(n1+n2*m1)%p;
					m1=(m1*m2)%p;
				}
				n2=(n2+n2*m2)%p;
				m2=(m2*m2)%p;
				n/=2;
			}
			if(n1==0){
				hit=true;
				break;
			}
		}
		if(hit==true){
			printf("%d %d\n",c+1,p);
			c++;
			ans+=p;
		}
		p+=2;
	}	
 	printf("ans=%d\n",ans);
}