1141-Dirichlet's Theorem on Arithmetic Progressions

考え方
実装するだけ
実装(C++)

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <ctime>
#include <cassert>
#include <cwchar>
#include <cstdarg>
#include <cwctype>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>

using namespace std;

typedef long long int lli;
typedef unsigned int uint;
long long mod_pow(long long a,long long n,long long M){
	if(n==0)return 1%M;
	long long res=mod_pow(a*a%M,n/2,M);
	if(n&1)res=res*a%M;
	return res;
}
bool miller_rabin(long long n){
	if(n==2)return true;if((n&1)==0||n<=1) return false;
	int a[]={2,3,5,7,11,13,17,-1},r;long long s=0,d,x;
	d=n-1;
	while((d&1)==0)s++,d=d>>1;
	for(int i=0;a[i]!=-1&&a[i]<n;i++){
		if((x=mod_pow(a[i],d,n))!=1){
			for(r=0;r<s;r++){
				if(x==n-1)break;
				x=(x*x)%n;
			}
			if(r==s)return false;
		}
	}
	return true;
}
int main(){
	int a,d,n,c;
	for(;cin>>a>>d>>n,a;){
		c=0;
		for(int i=a;;i+=d){
			if(miller_rabin(i))c++;
			if(c==n){
				cout<<i<<endl;
				break;
			}
		}
	}
	return 0;
}