結果

問題 No.368 LCM of K-products
コンテスト
ユーザー Hachimori
提出日時 2016-04-29 23:57:35
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 15 ms / 2,000 ms
コード長 2,158 bytes
コンパイル時間 800 ms
コンパイル使用メモリ 80,900 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-22 14:43:58
合計ジャッジ時間 1,780 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
const int PRIME = 100000;
const int NUM = 1005;
const int MOD = 1000000007;


int nPrime;
int prime[PRIME];

void makePrime() {
    bool isPrime[PRIME];
    for (int i = 0; i < PRIME; ++i) isPrime[i] = true;
    for (int i = 2; i * i < PRIME; ++i)
        if (isPrime[i])
            for (int j = i * 2; j < PRIME; j += i)
                isPrime[j] = false;
    nPrime = 0;
    for (int i = 2; i < PRIME; ++i)
        if (isPrime[i])
            prime[nPrime++] = i;
}


int nNum, nChoose;
int num[NUM];

void read() {
    cin >> nNum >> nChoose;
    for (int i = 0; i < nNum; ++i) {
        cin >> num[i];
    }
}


void addPrime2nFactor(int p, int nFactor, map<int, vector<int> > &prime2nFactor) {
    if (!prime2nFactor.count(p)) {
        prime2nFactor[p] = vector<int>();
    }
    prime2nFactor[p].push_back(nFactor);
}


int modpow(int p, int n) {
    if (n == 0) return 1;
    int t = modpow(p, n / 2);
    return n % 2 == 0 ? 1LL * t * t % MOD : 1LL * t * t % MOD * p % MOD;
}


void work() {
    map<int, vector<int> > prime2nFactor;
    
    for (int i = 0; i < nNum; ++i) {
        int n = num[i];
        
        for (int j = 0; prime[j] * prime[j] <= n; ++j) {
            if (n % prime[j] == 0) {
                int nFactor = 0;
                while (n % prime[j] == 0) {
                    n /= prime[j];
                    ++nFactor;
                }
                addPrime2nFactor(prime[j], nFactor, prime2nFactor);
            }
        }
        
        if (n > 1) {
            addPrime2nFactor(n, 1, prime2nFactor);
        }
    }

    int ans = 1;
    for (map<int, vector<int> >::iterator it = prime2nFactor.begin(); it != prime2nFactor.end(); ++it) {
        int prime = it->first;
        vector<int> &nFactor = it->second;

        sort(nFactor.rbegin(), nFactor.rend());

        for (int i = 0; i < min(nChoose, (int) nFactor.size()); ++i) {
            ans = (1LL * ans * modpow(prime, nFactor[i])) % MOD;
        }
    }
    
    cout << ans << endl;
}


int main() {
    makePrime();
    read();
    work();
    return 0;
}
0