うーむ。
https://community.topcoder.com/stat?c=problem_statement&pm=17160&rd=18868
問題
2桁以下の整数Pが与えられる。
D桁の整数のうち、(Dを文字列としてみなしたときの)Pの登場回数が最多タイになるようなものの総和を求めよ。
解法
素数判定が愚直にO(√N)かかるとすると、あとは候補をいかに絞り込むかという問題になる。
まずは、登場回数のパターンを数え上げよう。
Dの各桁について、Pの各桁と同じかそれと異なるか、3^|D|通りの組み合わせを考え、Pの登場回数を数えよう。
例えばP=12なら、"1""2""?"で構成されるD文字の文字列を考えてみるとよい。
その後、登場回数の多い順に、各パターンに該当する整数のうち素数のものを洗い出す。
const int prime_max = 1000000; vector<int> prime; int NP,divp[prime_max]; void cprime() { if(NP) return; 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]=i; } } //素数判定 bool isprime(ll v) { cprime(); int p; if(v==1) return 0; if(v==2) return 1; FORR(p,prime) { if(v%p==0) return 0; if(1LL*p*p>=v) return 1; } return 1; } const ll mo=1000000007; class PrettyPrimes { public: string P; vector<string> pat[13]; void dfs(int D,string C) { if(C.size()==D) { int i; int oc=0; for(i=0;i+P.size()<=C.size();i++) { if(C.substr(i,P.size())==P) oc++; } pat[oc].push_back(C); return; } C+="?"; dfs(D,C); C.back()=P[0]; dfs(D,C); if(P.size()==2&&P[0]!=P[1]) { C.back()=P[1]; dfs(D,C); } } ll hoge(string& p,int cur,ll v) { if(cur==p.size()) { if(isprime(v)) { return v; } else return 0; } if(p[cur]=='?') { ll sum=0; for(int i=0;i<10;i++) { if(cur==0&&i==0) continue; if(i==P[0]-'0') continue; if(i==P.back()-'0') continue; sum+=hoge(p,cur+1,v*10+i); } return sum%mo; } else { if(cur==0&&p[cur]=='0') return 0; return hoge(p,cur+1,v*10+p[cur]-'0'); } } int solve(int pattern, int D) { int i,j,x; FOR(i,12) pat[i].clear(); P=to_string(pattern); dfs(D,""); for(i=D;i>=0;i--) { ll sum=0; ll ok=0; FORR(a,pat[i]) { ll v=hoge(a,0,0); if(v) { (sum+=v)%=mo; ok=1; } } if(ok) return sum; } return 0%mo; } }
まとめ
けれ計算量どうなるんだろ。