結果

問題 No.1529 Constant Lcm
ユーザー spipipike
提出日時 2021-06-04 20:37:41
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,220 ms / 3,000 ms
コード長 1,270 bytes
コンパイル時間 2,112 ms
コンパイル使用メモリ 181,264 KB
実行使用メモリ 10,628 KB
最終ジャッジ日時 2024-11-19 09:40:29
合計ジャッジ時間 15,262 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
struct Sieve {
    int n;
    vector<int> f, primes;
    Sieve(int n=1):n(n), f(n+1) {
        f[0] = f[1] = -1;
        for (ll i = 2; i <= n; ++i) {
            if (f[i]) continue;
            primes.push_back(i);
            f[i] = i;
            for (ll j = i*i; j <= n; j += i) {
                if (!f[j]) f[j] = i;
            }
        }
    }
    bool isPrime(int x) { return f[x] == x;}
    vector<int> factorList(int x) {
        vector<int> res;
        while (x != 1) {
            res.push_back(f[x]);
            x /= f[x];
        }
        return res;
    }
    vector<P> factor(int x) {
        vector<int> fl = factorList(x);
        if (fl.size() == 0) return {};
        vector<P> res;
        int pre= -1;
        for (int p : fl) {
            if (pre == p) {
                res.back().second++;
            } else {
                res.emplace_back(p, 1);
            }
            pre=p;
        }
        return res;
    }
};
const int M=998244353;
int main(){
    int n;
    cin>>n;
    Sieve si(n);
    unordered_map<int, int> ma;
    for(int i=1; i<=n-1; i++){
        unordered_map<int, int> lma;
        for(P p : si.factor(i)) lma[p.first]+=p.second;
        for(P p : si.factor(n-i)) lma[p.first]+=p.second;
        for(P p : lma) ma[p.first]=max(ma[p.first], p.second);
    }
    int ans=1;
    for(P p : ma) rep(_, p.second) ans=(ll)ans*(p.first)%M;
    cout<<ans<<endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0