k개의 소수들의 곱을 순서대로 나열할 때, n번째로 오는 숫자를 구하는 문제이다.
가장 단순하게 k개의 소수들로 만들 수 있는 숫자들을 만든다는 전략을 사용해 보자.
i번째로 오는 수에 k개의 소수를 각각 곱하여 만들 수 있는 수를 우선순위큐에 넣어준다.
중복되는 경우가 있을 수 있기 때문에 하나의 경우만 있을 수 있도록 처리해 준다.
문제의 메모리가 적으므로 메모리 초과에 유의하자.
더보기
#define _CRT_SECURE_NO_WARNING
#include <bits/stdc++.h>
#include <ext/rope>
#include <cassert>
#include <x86intrin.h>
using namespace std;
using namespace __gnu_cxx;
// utils
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl "\n"
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define repair(x) x.erase(unique(all(x)),x.end())
typedef long long ll; //long long. or use int64_t
typedef long double ld; //long double
const int iinf = 1e9; //integer maximum
const long long linf = 1e18; //long long maximum
const int mod = 1e9 + 9; //prime number
// gcd, lcm, egcd funcs
template<class T>T gcd(T x, T y){if (!y)return x;return gcd(y,x%y);}
template<class T>T lcm(T x, T y){return (x*y)/gcd(x,y);}
// builtin funcs
template<class T>T bitcnt(T x){return __builtin_popcount(x);}
template<class T>T bitpar(T x){return __builtin_parity(x);}
template<class T>T bitclz(T x){return __builtin_clz(x);}
template<class T>T bitctz(T x){return __builtin_ctz(x);}
// debuging funcs
#define deb(x) cout<<#x<<": "<<(x)<<endl
//search for array
int dx[]={1,-1,0,0,0,0};
int dy[]={0,0,1,-1,0,0};
int dz[]={0,0,0,0,1,-1};
//////////////////////////////////////////
int k,n;
priority_queue<int,vector<int>,greater<int>>pq;
int main(){
fastio;
cin>>k>>n;
vector<int>arr(k);
for(auto&v:arr)cin>>v,pq.push(v);
for(int i=0; i<n-1; i++){
ll save=pq.top();
for(int j=0; j<k; j++){
if(save*arr[j]>=2147483647ll)continue;
pq.push(save*arr[j]);
}
while(pq.top()==save)pq.pop();
}
cout<<pq.top();
return 0;
}
'BOJ' 카테고리의 다른 글
BOJ 17433 - 신비로운 수 (0) | 2024.01.27 |
---|---|
BOJ 1437 - 수 분해 (0) | 2024.01.23 |
BOJ 17612 - 쇼핑몰 (1) | 2024.01.22 |
BOJ 30397 - 대구과학고등학교 (1) | 2023.11.14 |
BOJ 17971 - Ladder Game (0) | 2023.11.12 |