結果

問題 No.1529 Constant Lcm
ユーザー tarattata1tarattata1
提出日時 2021-06-04 22:17:03
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,985 ms / 3,000 ms
コード長 2,757 bytes
コンパイル時間 1,619 ms
コンパイル使用メモリ 105,448 KB
実行使用メモリ 77,312 KB
最終ジャッジ日時 2024-04-30 03:18:38
合計ジャッジ時間 21,611 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 3 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 1,719 ms
70,784 KB
testcase_11 AC 596 ms
29,860 KB
testcase_12 AC 19 ms
5,376 KB
testcase_13 AC 1,435 ms
61,056 KB
testcase_14 AC 837 ms
40,468 KB
testcase_15 AC 944 ms
42,752 KB
testcase_16 AC 724 ms
33,724 KB
testcase_17 AC 337 ms
19,928 KB
testcase_18 AC 375 ms
21,444 KB
testcase_19 AC 889 ms
41,416 KB
testcase_20 AC 1,938 ms
77,312 KB
testcase_21 AC 1,919 ms
77,312 KB
testcase_22 AC 1,918 ms
77,184 KB
testcase_23 AC 1,985 ms
77,312 KB
testcase_24 AC 1,945 ms
77,312 KB
testcase_25 AC 1,904 ms
77,312 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