結果

問題 No.368 LCM of K-products
ユーザー vjudge1vjudge1
提出日時 2024-08-17 18:28:29
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 6 ms / 2,000 ms
コード長 3,431 bytes
コンパイル時間 2,077 ms
コンパイル使用メモリ 184,212 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-08-17 18:28:33
合計ジャッジ時間 3,662 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
6,816 KB
testcase_01 AC 4 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 3 ms
6,940 KB
testcase_04 AC 3 ms
6,944 KB
testcase_05 AC 6 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,944 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,940 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 3 ms
6,944 KB
testcase_14 AC 3 ms
6,940 KB
testcase_15 AC 3 ms
6,940 KB
testcase_16 AC 3 ms
6,940 KB
testcase_17 AC 3 ms
6,944 KB
testcase_18 AC 3 ms
6,944 KB
testcase_19 AC 2 ms
6,944 KB
testcase_20 AC 3 ms
6,940 KB
testcase_21 AC 2 ms
6,940 KB
testcase_22 AC 3 ms
6,940 KB
testcase_23 AC 2 ms
6,940 KB
testcase_24 AC 2 ms
6,940 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,944 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,940 KB
testcase_33 AC 3 ms
6,944 KB
testcase_34 AC 2 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
#define For(i,l,r) for(int i=l;i<=r;i++)
#define _For(i,l,r) for(int i=r;i>=l;i--)
using namespace std;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
#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(j, 1, psize) {
    auto p = primes[j];
    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;
}
int main() {
    //open("lcm.in","lcm.out");
  const u32 MOD = 1e9 + 7;
  const u32 psize = init();
  u32 n, k;
  n=read(),k=read();
    map<u32, vector<u32> > cnts;
    rep(i, n) {
      u32 a; 
      a=read();
      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);
    return 0;
}
0