yukicoder No.368 LCM of K-products

問題

問題概要

Aの要素の中から、K個選んだ積のすべての要素の最小公倍数を求める。

解法

最小公倍数は、Bの要素を素因数分解したときの、各素因数に対して、Bの要素の中で最大の個数を持つものの積であらわされる。
今回の問題では、BはAの要素をK個選んだものの積であらわされるので、最小公倍数の中で、素数pがいくつ含まれるかを調べるには、Aの各要素を素因数分解したときの、素因数pを多く持つk個分の要素の素因数pの合計でわかる。これをすべての素数について行えばよい。

ミス

結構悩んだ。mapは便利だね。keyにも要素にもvector突っ込めるし。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;

ll powmod(ll x, ll k, ll m){
    if(k == 0) return 1;
    if(k % 2 == 0) return powmod(x * x % m, k / 2, m);
    else return x * powmod(x, k - 1, m) % m;
}

int main(void){
    int n, k; cin >> n >> k;
    map<int, vector<int> > m;

    rep(i, n){
        ll a; cin >> a;

        reps(j, 2, sqrt(a) + 1){
            int cnt = 0;
            while(a % j == 0){
                cnt++;
                a /= j;
            }
            if(cnt != 0){
                m[j].push_back(cnt);
            }
        }
        if(a != 1){//aが素数の時
            m[a].push_back(1);
        }
    }

    ll ans = 1;
    for(auto itr = m.begin(); itr != m.end(); ++itr){
        auto key = itr->first;
        auto v = itr->second;
        sort(all(v));
        reverse(all(v));

        int size = min(k, (int)v.size());
        rep(i, size){
            ans *= powmod(key, v[i], MOD);
            ans %= MOD;
        }
    }
    printf("%lld\n", ans % MOD);
    return 0;
}