yukicoder No.368 - LCM of K-products
解法
最終的には全てのの要素の最小公倍数だけが問題になります. この数を素因数分解したとき, 出てくる素数はの素因数のみです. またそれぞれの素数について, 指数が最大となるような個の要素を自由に選ぶことができます.
すなわち求める最小公倍数はを素因数分解して得られる素数それぞれについて, 指数の和が最大になるように貪欲にから個選び, それらを掛け合わせたものとなります.
ソースコード
#include <iostream> #include <map> #include <queue> #include <vector> using namespace std; typedef priority_queue<int, vector<int>, greater<int> > Queue; typedef long long ll; const ll kMOD = 1000 * 1000 * 1000 + 7; const int kMAX_N = 1010; const int kMAX_K = 1010; int N, K; ll a[kMAX_N]; ll GCD(ll a, ll b) { if (b == 0) return a; else return GCD(b, a % b); } ll LCM(ll a, ll b) { return a * b / GCD(a, b); } map<int, int> PrimeFactors(int n) { map<int, int> res; for (int i = 2; i * i <= n; i++) { while (n % i == 0) { res[i]++; n /= i; } } if (n != 1) res[n] = 1; return res; } void Solve() { map<int, Queue> biggest_factors; // 各素因数の最大の指数を記録する // 各素因数について, 素因数分解したときの最大の指数を貪欲にK個まで集める for (int i = 0; i < N; i++) { map<int, int> factors = PrimeFactors(a[i]); for (map<int, int>::iterator it = factors.begin(); it != factors.end(); it++) { if (biggest_factors.find(it->first) == biggest_factors.end()) { biggest_factors[it->first] = Queue(); } if (biggest_factors[it->first].size() < K) { biggest_factors[it->first].push(it->second); } else if (biggest_factors[it->first].top() < it->second) { biggest_factors[it->first].pop(); biggest_factors[it->first].push(it->second); } } } // 答えを計算 ll answer = 1; for (map<int, Queue>::iterator it = biggest_factors.begin(); it != biggest_factors.end(); it++) { while (!it->second.empty()) { int exponent = it->second.top(); it->second.pop(); for (int i = 0; i < exponent; i++) { answer *= it->first; answer %= kMOD; } } } cout << answer << endl; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N >> K; for (int i = 0; i < N; i++) { cin >> a[i]; } Solve(); return 0; }