結果

問題 No.368 LCM of K-products
ユーザー Min_25Min_25
提出日時 2016-05-04 04:33:10
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 6 ms / 2,000 ms
コード長 2,825 bytes
コンパイル時間 1,053 ms
コンパイル使用メモリ 101,472 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-22 14:45:16
合計ジャッジ時間 2,033 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
6,812 KB
testcase_01 AC 4 ms
6,944 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 3 ms
6,940 KB
testcase_04 AC 3 ms
6,940 KB
testcase_05 AC 6 ms
6,944 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 2 ms
6,944 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 3 ms
6,940 KB
testcase_14 AC 3 ms
6,940 KB
testcase_15 AC 3 ms
6,940 KB
testcase_16 AC 3 ms
6,944 KB
testcase_17 AC 3 ms
6,944 KB
testcase_18 AC 4 ms
6,944 KB
testcase_19 AC 2 ms
6,940 KB
testcase_20 AC 3 ms
6,940 KB
testcase_21 AC 2 ms
6,940 KB
testcase_22 AC 3 ms
6,944 KB
testcase_23 AC 2 ms
6,948 KB
testcase_24 AC 2 ms
6,944 KB
testcase_25 AC 2 ms
6,940 KB
testcase_26 AC 2 ms
6,944 KB
testcase_27 AC 2 ms
6,944 KB
testcase_28 AC 2 ms
6,940 KB
testcase_29 AC 2 ms
6,940 KB
testcase_30 AC 2 ms
6,944 KB
testcase_31 AC 2 ms
6,944 KB
testcase_32 AC 2 ms
6,944 KB
testcase_33 AC 2 ms
6,944 KB
testcase_34 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cassert>
#include <cmath>

#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>

#define _fetch(_1, _2, _3, _4, name, ...) name
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, b) rep4(i, a, b, 1)
#define rep4(i, a, b, c) for (int i = int(a); i < int(b); i += int(c))
#define rep(...) _fetch(__VA_ARGS__, rep4, rep3, rep2, _)(__VA_ARGS__)

#define getchar getchar_unlocked
#define putchar putchar_unlocked

using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u8 = unsigned char;
using f80 = long double;
using f64 = double;

u32 mul_inv(u32 n) {
  u32 x = n;
  x *= 2 - x * n; x *= 2 - x * n;
  x *= 2 - x * n; x *= 2 - x * n;
  return x;
}

struct ExactDiv {
  ExactDiv() {}
  ExactDiv(u32 n) : n(n), i(mul_inv(n)), t(u32(-1) / n) {}
  friend u32 operator / (u32 n, ExactDiv d) { return n * d.i; };
  bool divide(u32 n) { return n / *this <= this->t; }
  u32 n, i, t;
};

const int N = 1e9;
const int sqrt_N = sqrt(N);
ExactDiv primes[3500];
bool isprime[sqrt_N + 1];

u32 ctz(u32 n) {
  return __builtin_ctz(n);
}

using P = pair<u32, u32>;
vector<P> factors(u32 n, u32 psize) {
  auto ret = vector<P>();
  if (!(n & 1)) {
    u32 e = ctz(n);
    ret.emplace_back(2, e);
    n >>= e;
  }
  rep(pi, 1, psize) {
    auto p = primes[pi];
    if (p.n * p.n > n) break;
    if (p.divide(n)) {
      u32 e = 1; n = n / p;
      while (p.divide(n)) n = n / p, e++;
      ret.emplace_back(p.n, e);
    }
  }
  if (n > 1) ret.emplace_back(n, 1);
  return ret;
}

u32 init() {
  fill(isprime, isprime + sqrt_N + 1, 1);
  u32 v = sqrt(sqrt_N);
  rep(i, 2, v + 1) if (isprime[i]) rep(j, i * i, sqrt_N + 1, i) isprime[j] = 0;
  u32 psize = 0;
  rep(i, 2, sqrt_N + 1) if (isprime[i]) primes[psize++] = ExactDiv(i);
  primes[psize++] = sqrt_N + 1;
  return psize;
}

void solve() {
  const u32 MOD = 1e9 + 7;
  const u32 psize = init();
  u32 n, k;
  while (~scanf("%u %u", &n, &k)) {
    map<u32, vector<u32> > cnts;
    rep(i, n) {
      u32 a; scanf("%u", &a);
      for (auto& p : factors(a, psize)) {
        if (cnts.find(p.first) != cnts.end()) {
          cnts[p.first].push_back(p.second);
        } else {
          cnts[p.first] = vector<u32>(1, p.second);
        }
      }
    }
    u32 ans = 1;
    for (auto& pp : cnts) {
      auto p = pp.first;
      auto& v = pp.second;
      sort(v.begin(), v.end());
      u32 e = 0;
      rep(i, min(u32(v.size()), k)) {
        e += v[v.size() - 1 - i];
      }
      rep(i, e) ans = u64(ans) * p % MOD;
    }
    printf("%u\n", ans);
  }
}

int main() {
  // clock_t beg = clock();
  solve();
  // clock_t end = clock();
  // fprintf(stderr, "%.3f sec.\n", double(end - beg) / CLOCKS_PER_SEC);
  return 0;
}
0