[Codeforces] 912E. Prime Gift

題目連結:http://codeforces.com/contest/912/problem/E

---

記錄一下覺得滿有趣的題目。 首先要知道$10^{18}$以內的只包含包個質因數的數，大約只有$10^6~10^7$種左右，所以我們可以把給定的$n$個質數採用砍半枚舉產生出所有$10^{18}$以內僅包含給定的質因數的數，但是因為如果真的把全部都長出來了會太大，所以我們還可以二分搜第k大會是誰，這樣就只要知道比某個數小的數字有幾個就好了，而計算這個的方法很簡單，就枚舉一邊，再二分搜另外一邊即可。

#include <bits/stdc++.h>
using namespace std;
typedef uint64_t llu;
#define PB push_back
#define ALL(x) begin(x), end(x)
const llu C = 1000000000000000000LL;

llu primes[20], p1[10], p2[10];
vector<llu> num1, num2;

inline llu calc(llu);
void dfs(int,llu,llu[],int,vector<llu>&);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n; cin>>n;
	for(int i=0;i<n;i++) cin>>primes[i];
	sort(primes, primes+n);
	int n1 = 0, n2 = 0;
	for(int i=0;i<n;i+=2) p1[n1++] = primes[i];
	for(int i=1;i<n;i+=2) p2[n2++] = primes[i];
	dfs(0, 1, p1, n1, num1);
	dfs(0, 1, p2, n2, num2);
	sort(ALL(num1)); num1.resize(distance(num1.begin(), unique(ALL(num1))));
	sort(ALL(num2)); num2.resize(distance(num2.begin(), unique(ALL(num2))));
	llu k; cin>>k;
	llu l = 0, r = C;
	while(r-l > 1){
		llu mid = (l+r)>>1;
		if(calc(mid) >= k) r = mid;
		else l = mid;
	}
	cout << r << '\n';
	return 0;
}

void dfs(int id, llu x, llu p[], int n, vector<llu>& ret){
	if(x > C) return;
	if(id==n){
		ret.PB(x);
		return;
	}
	dfs(id+1, x, p, n, ret);
	if(x <= C/p[id]) dfs(id, x*p[id], p, n, ret);
}

inline llu calc(llu x){
	llu ret = 0;
	for(auto i: num1){
		llu dis = distance(num2.begin(), upper_bound(ALL(num2), x/i));
		if(dis == 0) break;
		ret += dis;
	}
	return ret;
}