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

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20130
Problem 130 「素数桁レピュニットと同じ性質を持つ合成数」 †
1からのみなる数をレピュニットと呼ぶ. R(k)で長さkのレピュニットを表す. 例えばR(6) = 111111である.

GCD(n, 10) = 1 となる正整数 n について, 必ず正整数 k が存在し n が R(k) を割り切ることが証明できる. A(n) でそのような最小の k を表す. 例: A(7) = 6. A(41) = 5.

5より大きい素数 p について, A(p) が p - 1 を割り切ることが知られている. p = 41 のときには, A(41) = 5 であり, 40は5で割り切れる.

非常に少ないのだが, 合成数においても上が成立する場合がある. 最初の5つの例は 91, 259, 451, 481, 703 である.

GCD(n, 10) = 1 かつ A(n) が n - 1 を割り切るような最初の25個の合成数 n の総和を求めよ.

解法
検証したい数をｎをｍ＝fai（ｎ*9）に入れ、10＾ｍの約数乗とｎ*9の余りをとると答えが検証可能。
何の説明にもなってないな。
私は暗黙知だけで問題を解いているから人に説明はできない。
直感的に解いている。

#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
using namespace std;

int fai(int n){
std::vector<int> vec;
int m=n;
for(int i=2;i*i<=m&&i<=n;i++){
	if(n%i==0){
		vec.push_back(i);
		while(n%i==0){
			n/=i;
		}
	}
}
if(n>1)vec.push_back(n);
for(int i=0;i<vec.size();i++){
	m=m/vec[i]*(vec[i]-1);
}
return m;
}

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

int modPow(long long int n,int p){
long long int m=10,r=1;
while(p>0){
	if(p%2==1){
		r=(m*r)%n;
	}
	p/=2;
	m=(m*m)%n;
}
return r;
}

int main() {
// your code goes here
int count=0,ans=0;
for(int i=91;count<25;i++){
	if(isPrime(i)==true)continue;
	if(i%2==0||i%5==0)continue;
	int n=i*9;
	int m=fai(n);
	int a=n;
	for(int j=1;j*j<=m;j++){
		if(m%j==0&&modPow(n,j)==1){
			a=j;
			break;
		}
	}
	for(int j=1;j*j<=m;j++){
		if(m%j==0&&modPow(n,m/j)==1){
			a=std::min(a,m/j);
		}
	}	
	if((i-1)%a==0){
		count++;
		ans+=i;
		printf("%d\n",i);
	}
}
printf("ans=%d\n",ans);
return 0;
}