#1187567 (C++17) No.3717 GCD LCM GCD

• 問題: No.3717 GCD LCM GCD
• ユーザー: 👑 Nachia
• 提出日時: 2026-09-18 21:53:29
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 50 ms / 2,000 ms
• コード長: 3,686 bytes
• コンパイル時間: 442 ms
• コンパイル使用メモリ: 94,076 KB
• 実行使用メモリ: 26,880 KB
• 最終ジャッジ日時: 2026-09-18 21:54:05
• 合計ジャッジ時間: 2,591 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	AC * 4
other	AC * 8

ソースコード

#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
// disable assert
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const ll INF = 1ll << 60;
#define REP(i,n) for(ll i=0; i<ll(n); i++)
template <class T> using V = vector<T>;
template <class A, class B> void chmax(A& l, const B& r){ if(l < r) l = r; }
template <class A, class B> void chmin(A& l, const B& r){ if(r < l) l = r; }


#include <utility>

#include <cassert>
namespace nachia{

// ax + by = gcd(a,b)
// return ( x, - )
std::pair<long long, long long> ExtGcd(long long a, long long b){
    long long x = 1, y = 0;
    while(b){
        long long u = a / b;
        std::swap(a-=b*u, b);
        std::swap(x-=y*u, y);
    }
    return std::make_pair(x, a);
}

} // namespace nachia

namespace nachia{

template<unsigned int MOD>
struct StaticModint{
private:
    using u64 = unsigned long long;
    unsigned int x;
public:

    using my_type = StaticModint;
    template< class Elem >
    static Elem safe_mod(Elem x){
        if(x < 0){
            if(0 <= x+MOD) return x + MOD;
            return MOD - ((-(x+MOD)-1) % MOD + 1);
        }
        return x % MOD;
    }

    StaticModint() : x(0){}
    StaticModint(const my_type& a) : x(a.x){}
    StaticModint& operator=(const my_type&) = default;
    template< class Elem >
    StaticModint(Elem v) : x(safe_mod(v)){}
    unsigned int operator*() const { return x; }
    my_type& operator+=(const my_type& r) { auto t = x + r.x; if(t >= MOD) t -= MOD; x = t; return *this; }
    my_type operator+(const my_type& r) const { my_type res = *this; return res += r; }
    my_type& operator-=(const my_type& r) { auto t = x + MOD - r.x; if(t >= MOD) t -= MOD; x = t; return *this; }
    my_type operator-(const my_type& r) const { my_type res = *this; return res -= r; }
    my_type operator-() const noexcept { my_type res = *this; res.x = ((res.x == 0) ? 0 : (MOD - res.x)); return res; }
    my_type& operator*=(const my_type& r){ x = (u64)x * r.x % MOD; return *this; }
    my_type operator*(const my_type& r) const { my_type res = *this; return res *= r; }
    bool operator==(const my_type& r) const { return x == r.x; }
    my_type pow(unsigned long long i) const {
        my_type a = *this, res = 1;
        while(i){ if(i & 1){ res *= a; } a *= a; i >>= 1; }
        return res;
    }
    my_type inv() const { return my_type(ExtGcd(x, MOD).first); }
    unsigned int val() const { return x; }
    int hval() const { return int(x > MOD/2 ? x - MOD : x); }
    static constexpr unsigned int mod() { return MOD; }
    static my_type raw(unsigned int val) { auto res = my_type(); res.x = val; return res; }
    my_type& operator/=(const my_type& r){ return operator*=(r.inv()); }
    my_type operator/(const my_type& r) const { return operator*(r.inv()); }
};

} // namespace nachia
using Mint = nachia::StaticModint<998244353>;

void testcase(){
  ll Z = 1000000;

  ll N, K; cin >> N >> K;
  V<ll> cnt(Z+1, 0);
  REP(i,N){
    ll a; cin >> a;
    cnt[a]++;
  }
  V<ll> mcnt(Z+1, 0);
  for(ll i=1; i<=Z; i++) for(ll j=i; j<=Z; j+=i) mcnt[i] += cnt[j];
  V<ll> kiyo(Z+1, 1); kiyo[0] = kiyo[1] = 0;
  for(ll p=2; p<=Z; p++) if(kiyo[p] == 1){
    for(ll q=p; q<=Z; q+=p) kiyo[q] = 0;
    for(ll q=p; q<=Z; q*=p) kiyo[q] = p;
  }

  // for(ll i=1; i<=Z; i++) cout << mcnt[i] << " "; cout << endl;
  // for(ll i=1; i<=Z; i++) cout << kiyo[i] << " "; cout << endl;
  Mint ans = 1;
  for(ll i=1; i<=Z; i++) if(kiyo[i] > 1){
    if((N - mcnt[i]) * K + (K - 1) < N) ans *= kiyo[i];
  }
  cout << ans.val() << "\n";
}

int main(){
  cin.tie(0)->sync_with_stdio(0);
  testcase();
  return 0;
}