結果

問題 No.368 LCM of K-products
ユーザー lam6er
提出日時 2025-03-26 16:01:39
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 6 ms / 2,000 ms
コード長 3,431 bytes
コンパイル時間 2,360 ms
コンパイル使用メモリ 209,572 KB
実行使用メモリ 7,324 KB
最終ジャッジ日時 2025-03-26 16:01:56
合計ジャッジ時間 3,722 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0