Codeforces #456 Div2 E. Prime Gift

これが解けないのはまずかったなぁ…。
http://codeforces.com/contest/912/problem/E

問題

N個の異なる素数の集合Pが与えられる。
自然数のうち、素因数分解して得られる素因数がPに含まれるものだけであるようなものを考え、それを昇順に並べた数列を考える。
そのうちK番目の要素を答えよ。
なお、K番目は10^18以下であることが保障されている。

解法

条件を満たす数列は、10^18以下の要素に限っても結構数が多い場合があり、列挙するとTLE/MLEしてしまう。
そこで半分全列挙+二分探索で求めよう。

v以下の整数のうち、条件の数列に含まれる要素数をf(v)としたとき、f(v)は単調増加なので、二分探索でf(v)=Kを満たすvの最小値を答えればよい。
あとはf(v)の求め方である。
こちらは半分全列挙で求めよう。

Pのうち半分について、それらを掛け合わせて作れる10^18以下の整数を列挙しよう。これはDFS等で行える。
同様に残り半分についても列挙する。
前者の数列をA,後者をBをする。A,Bは事前に昇順ソートしておく。
各a∈Aについて、lower_bound等でv/a以下の要素数を数えれば、合わせてv以下である値を数え上げられる。

int N;
ll P[101];
ll K;
ll pro[1<<16];
ll num[1<<16];

vector<ll> A,B;
void dfs(ll v,int id,int mid, vector<ll>& V) {
	if(v>=1LL<<60) return;
	V.push_back(v);
	for(int i=id;i<mid;i++) if(v*P[i]/P[i]==v) dfs(v*P[i],i,mid,V);
}

ll hoge(ll v, ll k) {
	ll ret=0;
	FORR(a,A) {
		ret += lower_bound(ALL(B),v/a+1)-B.begin();
		if(ret>=k) return ret;
	}
	return ret;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,16) {
		if(i<N) cin>>P[i];
		else P[i]=1LL<<60;
	}
	
	cin>>K;
	dfs(1,0,8,A);
	dfs(1,8,16,B);
	
	sort(ALL(A));
	sort(ALL(B));
	if(A.size()>B.size()) swap(A,B);
	
	ll ret=1LL<<60;
	for(i=59;i>=0;i--) if(hoge(ret-(1LL<<i),K)>=K) ret-=1LL<<i;
	cout<<ret<<endl;
	
}

まとめ

本番なぜ二分探索でダメだと思ってしまったんだろう。