結果

問題 No.1529 Constant Lcm
ユーザー tarattata1tarattata1
提出日時 2021-06-04 22:17:03
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 1,816 ms / 3,000 ms
コード長 2,757 bytes
コンパイル時間 1,031 ms
コンパイル使用メモリ 104,980 KB
実行使用メモリ 77,024 KB
最終ジャッジ日時 2023-08-12 13:30:01
合計ジャッジ時間 20,269 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 3 ms
4,380 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 1,613 ms
70,720 KB
testcase_11 AC 544 ms
29,484 KB
testcase_12 AC 17 ms
4,428 KB
testcase_13 AC 1,344 ms
60,756 KB
testcase_14 AC 778 ms
40,176 KB
testcase_15 AC 885 ms
42,416 KB
testcase_16 AC 650 ms
33,320 KB
testcase_17 AC 313 ms
19,588 KB
testcase_18 AC 327 ms
20,892 KB
testcase_19 AC 818 ms
41,172 KB
testcase_20 AC 1,816 ms
76,980 KB
testcase_21 AC 1,785 ms
76,972 KB
testcase_22 AC 1,793 ms
76,860 KB
testcase_23 AC 1,811 ms
77,024 KB
testcase_24 AC 1,810 ms
77,000 KB
testcase_25 AC 1,724 ms
76,984 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <cassert>
#include <numeric>
#include <functional>
#include <ctime>
#pragma warning(disable:4996) 

//#define ATCODER
#ifdef ATCODER
#include <atcoder/all>
#endif

typedef long long ll;
typedef unsigned long long ull;
#define LINF  9223300000000000000
#define LINF2 1223300000000000000
#define LINF3 1000000000000
#define INF 2140000000
//const long long MOD = 1000000007;
const long long MOD = 998244353;

using namespace std;
#ifdef ATCODER
using namespace atcoder;
#endif


ll mpow(ll x, ll n) { //x^n(mod M)
    ll ans = 1;
    while (n != 0) {
        if (n & 1) ans = ans * x % MOD;
        x = x * x % MOD;
        n = n >> 1;
    }
    return ans;
}

void decompositAll(int n, vector<vector<pair<int, int>>>& dec)      // n以下を全て素因数分解   例：dec[12]={(2,2),(3,1)}
{
    dec.resize(n + 1);
    vector<int> f(n + 1);
    int i;
    for (i = 2; i <= n; i++) {
        if (f[i] == 0) {
            int i2 = i;
            while (i2 <= n) {
                int j = i2;
                while (j <= n) {
                    f[j] = 1;
                    if (!dec[j].empty() && dec[j].back().first == i) {
                        dec[j].back().second++;
                    }
                    else {
                        dec[j].push_back(make_pair(i, 1));
                    }
                    j += i2;
                }
                if ((ll)i2*i > n) break;
                i2 = i2 * i;
            }
        }
    }
    return;
}

void solve()
{
    int n;
    scanf("%d", &n);

    vector<vector<pair<int, int>>> dec;
    decompositAll(n, dec);

    ll ans = 1;
    map<int, int> z;
    for (int i = 1; i <= n - 1; i++) {
        vector<pair<int, int>>& v0 = dec[i];
        vector<pair<int, int>>& v1 = dec[n-i];
        map<int,int> s0;
        for (int k = 0; k < (int)v0.size(); k++) {
            s0[v0[k].first] = v0[k].second;
        }
        for (int k = 0; k < (int)v1.size(); k++) {
            s0[v1[k].first]+=v1[k].second;
        }

        auto it = s0.begin();
        for(;it!=s0.end();++it){
            z[it->first] = max(z[it->first], it->second);
        }
    }
    auto it = z.begin();
    for (; it != z.end(); ++it) {
        int p = it->first;
        int num = it->second;
        ans = ans * mpow(p, num) %MOD;
    }
    printf("%lld\n", ans);

    return;
}

int main()
{
#if 1
    solve();
#else
    int T, t;
    scanf("%d", &T);
    for (t = 0; t < T; t++) {
        //printf("Case #%d: ", t + 1);
        solve();
    }
#endif
    return 0;
}
0