[Codeforces] 912E. Prime Gift
題目連結:http://codeforces.com/contest/912/problem/E
記錄一下覺得滿有趣的題目。 首先要知道$10^{18}$以內的只包含包個質因數的數,大約只有$10^6~10^7$種左右,所以我們可以把給定的$n$個質數採用砍半枚舉產生出所有$10^{18}$以內僅包含給定的質因數的數,但是因為如果真的把全部都長出來了會太大,所以我們還可以二分搜第k大會是誰,這樣就只要知道比某個數小的數字有幾個就好了,而計算這個的方法很簡單,就枚舉一邊,再二分搜另外一邊即可。
記錄一下覺得滿有趣的題目。 首先要知道$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;
}
留言
張貼留言