本番これ出たらいやだな…。
https://community.topcoder.com/stat?c=problem_statement&pm=16251&rd=18068
問題
正整数N,Kが与えられる。
N桁の正整数のうち、どこのK桁を抜き出してもLeading Zeroを含まない素数になっているものを求めよ。
解法
K桁の素数をリピートしたものを総当たりすると、K=7以外は回答できる。
K=7の時7桁の素数で条件を満たすものはないが、8桁の素数まで見ると解がある。
const int prime_max = 10000000; vector<int> prime; int NP; bool divp[prime_max]; void cprime() { if(NP) return; divp[1]=1; for(int i=2;i<prime_max;i++) if(divp[i]==0) { //M[i]=NP; prime.push_back(i); NP++; for(ll j=1LL*i*i;j>=i&&j<prime_max;j+=i) if(divp[j]==0) divp[j]=1; } } class PrimeSubstrings { public: int L; int ok(int p,int L) { string S=to_string(p),T; while(T.size()<S.size()+L) T+=S; int i; FOR(i,S.size()) { if(T[i]=='0') return 0; int v=atoi(T.substr(i,L).c_str()); if(divp[v]) return 0; } return 1; } int dfs(int p,int d) { if(ok(p,L)) return p; if(d==8) return 0; int i,v; FOR(i,5) { v=dfs(p*10+i*2+1,d+1); if(v) return v; } return 0; } string construct(int N, int L) { this->L=L; cprime(); string S=to_string(dfs(0,0)),T; int i; FOR(i,N) T+=S[i%S.size()]; return T; } }
まとめ
2Bといい2Aといいしんどい問題。