#1189364 (C++23) No.3717 GCD LCM GCD

• 問題: No.3717 GCD LCM GCD
• ユーザー: MaTi
• 提出日時: 2026-09-19 17:33:15
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 606 ms / 2,000 ms
• コード長: 3,741 bytes
• コンパイル時間: 2,092 ms
• コンパイル使用メモリ: 337,132 KB
• 実行使用メモリ: 12,712 KB
• 最終ジャッジ日時: 2026-09-19 17:33:22
• 合計ジャッジ時間: 3,968 ms
• ジャッジサーバーID （参考情報）: judge4_1 / judge2_0

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

ソースコード

#include <bits/stdc++.h>
// #include <atcoder/all>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define rep(i,a,b) for (ll i=a; i<b; i++)
#define rrep(i,a,b) for(ll i=a; i>=b; i--)
#define fore(i,a) for(auto &i:a)
#define pb push_back
#define _GLIBCXX_DEBUG
#define All(a) (a).begin(), (a).end()
#define YN(a) ((a) ? "Yes" : "No")
template <typename T> inline bool chmin(T& a, const T& b) {bool c=a>b; if(a>b) a=b; return c;}
template <typename T> inline bool chmax(T& a, const T& b) {bool c=a<b; if(a<b) a=b; return c;}
template <typename T> inline T gcd(T a,T b) {return (b==0)?a:gcd(b,a%b);}
template <typename T> inline T lcm(T a, T b) {return (a*b)/gcd(a,b);}
const int inf = INT_MAX / 2;
const ll linf = 1LL << 61;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvvi = vector<vector<vector<int>>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using vvvll = vector<vector<vector<ll>>>;

template <typename T>
void OUT(const T& x) {
    cout << x;
}
// ----- pair -----
template <typename T, typename U>
void OUT(const pair<T,U>& p) {
    cout << "(";
    OUT(p.first);
    cout << ", ";
    OUT(p.second);
    cout << ")";
}
// ----- vector -----
template <typename T>
void OUT(const vector<T>& v) {
    cout << "[ ";
    for (const auto& x : v) {
        OUT(x);
        cout << " ";
    }
    cout << "]";
}
// ----- set -----
template <typename T>
void OUT(const set<T>& s) {
    cout << "{ ";
    for (const auto& x : s) {
        OUT(x);
        cout << " ";
    }
    cout << "}";
}
// ----- map -----
template <typename K, typename V>
void OUT(const map<K,V>& mp) {
    cout << "{ ";
    for (const auto& [k,v] : mp) {
        OUT(k);
        cout << ": ";
        OUT(v);
        cout << ", ";
    }
    cout << "}";
}
// ----- queue -----
template <typename T>
void OUT(queue<T> q) {
    cout << "< ";
    while (!q.empty()) {
        OUT(q.front());
        cout << " ";
        q.pop();
    }
    cout << ">";
}
// ----- priority_queue -----
template <typename T>
void OUT(priority_queue<T> pq) {
    cout << "< ";
    while (!pq.empty()) {
        OUT(pq.top());
        cout << " ";
        pq.pop();
    }
    cout << ">";
}
// ----- stack -----
template <typename T>
void OUT(stack<T> st) {
    cout << "< ";
    while (!st.empty()) {
        OUT(st.top());
        cout << " ";
        st.pop();
    }
    cout << ">";
}
// ----- deque -----
template <typename T>
void OUT(const deque<T>& dq) {
    cout << "[ ";
    for (const auto& x : dq) {
        OUT(x);
        cout << " ";
    }
    cout << "]";
}
#define out(x) cerr << #x << ": ", OUT(x), cerr << '\n';

ll pow(ll a, ll n){
    ll ans = 1;
    rep(i,0,n){
        ans *= a;
    }
    return ans;
}

ll MOD = 998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n,k;
    cin >> n >> k;
    vll divs((1e+6)+1,0);
    vll avec(n);
    rep(i,0,n){
        ll a;
        cin >> a;
        avec[i] = a;
        if(a == 1) continue;
        for(ll j = 2; j*j <= a; ++j){
            if(a%j != 0) continue;
            ll ex = 0;

            while(a%j == 0){
                ex ++;
                a /=j;
                divs[pow(j,ex)] ++;
            }
        }
        if(a != 1) divs[a] ++;
    }
    ll lim = n - ((n/k) - 1);
    ll ans = 1;
    // rep(i,0,10){
    //     cout << divs[i] << endl;
    // }
    if(k==1){
        rep(i,0,n){
            ans = ans * (avec[i]/gcd(avec[i],ans));
            ans %= MOD;
        }
    }else {
        rrep(i,1e+6,0){
            if(divs[i] >= lim and ans%i != 0){
                ans *= i;
            }
            ans %= MOD;
        }
    }

    cout << ans<< endl;
    cout << fixed << setprecision(30);
    return 0;
}