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

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20129
Problem 129 「レピュニットの非整除性」 †
1のみからなる数をレピュニットという. R(k) を長さ k のレピュニットとする. 例えば, R(6) = 111111 となる.

GCD(n, 10) = 1 なる正の整数 n が与えられたとき, R(k) が n で割り切られるような k が常に存在することが示せる. A(n) をそのような k の最小のものとする. 例えば, A(7) = 6, A(41) = 5 となる.

A(n) の値が10を超える最小の n は17である.

A(n) の値が100万を超える最小の n を求めよ.

解法
元の数を９倍してオイラーの定理（数論）を適用して試してみれば答えが出ます。

#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;
}

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
for(int i=1000*1000;i<1000*1000+50;i++){
	int n=i*9;
	int ans=n;
	int m=fai(n);
	for(int j=1;j*j<=m;j++){
		if(m%j==0&&modPow(n,j)==1){
			ans=j;
                          break;
		}
	}
	for(int j=1;j*j<=m;j++){
		if(m%j==0&&modPow(n,m/j)==1){
			ans=std::min(ans,m/j);
		}
	}	
	if(ans!=n&&ans>1000*1000){
		printf("%d\n",i);
		break;
	}
}
return 0;
}