TopCoderOpen 2019 Round3B : Medium PrefixComposite

450ptなので比較的Mediumの割に易しめ。
https://community.topcoder.com/stat?c=problem_statement&pm=15603&rd=17617

問題

ある整数がprefix-compositeであるとは、整数の10進数表記を文字列とみなしたとき、prefixに相当する整数がいずれも合成数であることをいう。
区間[A,B]が与えられる。区間内で最小と最大のprefix-compositeを求めよ。

解法

整数が与えられたときのprefix-composite判定は定義通り愚直にprefixの素数判定をすればよい。
後は、
「v以上最小のprefix-composite」「v以下最大のprefix-composite」を効率よく求めていくことを考えよう。

まずv以上最小のprefix-compositeについて。
v=abcdeとしたとき、abcが素数だとしたら、ab(c+1)00という形に置き換える、ということを繰り返そう。
全桁4以上の偶数なら確実に条件を満たすので、置き換え回数はさほど多くならない。

v以下最大のprefix-compositeについても、abcde→ab(c-1)99のように置き換えていけばよい。

class PrefixComposite {
	public:
	ll p10[13];
	
	bool isprime(ll v) {
		if(v==1) return 1;
		for(ll i=2;i*i<=v;i++) if(v%i==0) return false;
		return (v!=1);
	}
	
	ll getmore(ll v) {
		vector<ll> V;
		ll w=v;
		while(w) {
			V.push_back(w);
			w/=10;
		}
		reverse(ALL(V));
		int i;
		FOR(i,V.size()) if(isprime(V[i])) {
			return getmore((V[i]+1)*p10[V.size()-1-i]);
		}
		return v;
		
	}
	ll getless(ll v) {
		if(v<=3) return -1;
		vector<ll> V;
		ll w=v;
		while(w) {
			V.push_back(w);
			w/=10;
		}
		reverse(ALL(V));
		int i;
		FOR(i,V.size()) if(isprime(V[i])) {
			ll nv=V[i]*p10[V.size()-1-i];
			if(nv<v) return getless(nv);
			else return getless(nv-1);
		}
		return v;
	}
	
	vector<long long> minMax(long long A, long long B) {
		p10[0]=1;
		int i;
		FOR(i,12) p10[i+1]=p10[i]*10;
		
		ll a = getmore(A);
		ll b = getless(B);
		
		
		
		if(a>b) return {};
		return {a,b};
	}
}

まとめ

これ計算量どうなるんだろう。