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