Project Euler Problem 134

問題文

解法

Modの世界での方程式を立てて解く．
例えば19,23なら100x+19≡0(MOD 23)となる．

実装(C++)

tools.hについてはgithub参照

#include <iostream>
#include <ctime>
#include <iomanip>
#include <algorithm>
#include <vector>
#include "tools.h"
using namespace std;

long calc(int p1,int p2){
	long q=1;;
	while(q<p1)q*=10;

	long a=q%p2;
	long b=(p2-p1)%p2;
	long r=mod_inverse(a,p2);
	return q*((b*r)%p2)+p1;
}
long solve(){
	long sum=0;
	vector<int> primes=prime_list(1010000);
	for(int i=0;i<(int)primes.size();i++){
		if(primes[i]>=5&&primes[i]<=1000000){
			sum+=calc(primes[i],primes[i+1]);
			cout<<calc(primes[i],primes[i+1])<<endl;
		}
	}
	return sum;
}
int main(){
	clock_t start;
	start=clock();

	cout<<"---"<<endl<<"Answer:"<<solve()<<endl;
	cout<<"Calculation Time:"<<(clock()-start)/(double)CLOCKS_PER_SEC<<endl;
}