結果
問題 | No.1529 Constant Lcm |
ユーザー | noya2 |
提出日時 | 2021-06-04 20:47:29 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 862 ms / 3,000 ms |
コード長 | 3,930 bytes |
コンパイル時間 | 4,932 ms |
コンパイル使用メモリ | 274,356 KB |
実行使用メモリ | 57,844 KB |
最終ジャッジ日時 | 2024-04-30 00:27:54 |
合計ジャッジ時間 | 13,658 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 1 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 | 1 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 759 ms
53,120 KB |
testcase_11 | AC | 265 ms
23,296 KB |
testcase_12 | AC | 11 ms
5,376 KB |
testcase_13 | AC | 621 ms
45,952 KB |
testcase_14 | AC | 377 ms
30,976 KB |
testcase_15 | AC | 415 ms
32,640 KB |
testcase_16 | AC | 309 ms
26,112 KB |
testcase_17 | AC | 155 ms
15,872 KB |
testcase_18 | AC | 177 ms
16,896 KB |
testcase_19 | AC | 392 ms
31,744 KB |
testcase_20 | AC | 862 ms
57,728 KB |
testcase_21 | AC | 845 ms
57,616 KB |
testcase_22 | AC | 831 ms
57,728 KB |
testcase_23 | AC | 857 ms
57,844 KB |
testcase_24 | AC | 824 ms
57,728 KB |
testcase_25 | AC | 787 ms
57,680 KB |
ソースコード
#include <bits/stdc++.h> /* #include <boost/multiprecision/cpp_dec_float.hpp> #include <boost/multiprecision/cpp_int.hpp> namespace mp = boost::multiprecision; using bint = mp::cpp_int; */ #include <atcoder/all> #include <iostream> #include <queue> #include <stack> #include <vector> #include <string> #include <set> #include <map> #include <random> #include <bitset> #define rep(i,n) for (int i = 0; i < int(n); ++i) #define repp(i,n,m) for (int i = m; i < int(n); ++i) using namespace std; using namespace atcoder; using namespace internal; //alias g++='g++ -I/mnt/c/Users/Owner/Desktop/ac-library' using ll = long long; using ld = long double; using P = pair<int, int>; using PI = pair<pair<int,int>,int>; using PL = pair<long long, long long>; using PLL = pair<pair<long long, long long>, long long>; using Pxy = pair<long double, long double>; const int INF = 1001001007; const int modd = 1000000007; const long long modl = 1000000007LL; const long long mod = 998244353LL; const ll inf = 2e18; template <typename SA> void priv(vector<SA> &ar){ if (ar.size() == 0) cout << endl; else { rep(i,ar.size()-1) cout << ar[i] << " "; cout << ar[ar.size()-1] << endl; } } template <typename SB> void privv(vector<vector<SB>> &ar){ rep(i,ar.size()){ rep(j,ar[i].size()-1) cout << ar[i][j] << " "; cout << ar[i][ar[i].size()-1] << endl; } } template <typename SC> bool range(SC a, SC b, SC x){return (a <= x && x < b);} bool rrange(P a, P b, P xy){ bool s = range(a.first,b.first,xy.first); bool t = range(a.second,b.second,xy.second); return (s && t); } template <typename SD> void sor(vector<SD> &ar){sort(ar.begin(),ar.end());} template <typename SE> void rev(vector<SE> &ar){reverse(ar.begin(),ar.end());} template <typename SF> bool chmin(SF &a, const SF &b){if(a>b){a = b; return true;} return false;} template <typename SG> bool chmax(SG &a, const SG &b){if(a<b){a = b; return true;} return false;} template <typename SH> void eru(vector<SH> &ar){sor(ar);ar.erase(unique(ar.begin(),ar.end()),ar.end());} template <typename SI> SI last(vector<SI> &ar){return ar[ar.size()-1];} template <typename SJ> SJ cel(SJ a, SJ b){if (a % b == 0) return a/b; return a/b +1;} template <typename SK, typename SL> void pout(pair<SK,SL> p) {cout << p.first << " " << p.second << endl;} void yes(){cout << "Yes" << endl;} void no (){cout << "No" << endl;} void yn (bool t){if(t)yes();else no();} void Yes(){cout << "YES" << endl;} void No (){cout << "NO" << endl;} void YN (bool t){if(t)Yes();else No();} void dout() {cout << setprecision(20);} vector<int> dx = {0,1,0,-1}; vector<int> dy = {1,0,-1,0}; const string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const string alp = "abcdefghijklmnopqrstuvwxyz"; ll gcds(ll a, ll b){ ll c = a % b; while (c != 0){ a = b; b = c; c = a % b; } return b; } int main(){ int n; cin >> n; vector<int> div(n+1,-1); set<int> st; repp(i,n+1,2) st.insert(i); repp(i,n+1,2){ if (div[i] != -1) continue; for (int j = i; j <= n; j += i){ if (div[j] == -1) div[j] = i; } } map<int,int> mp; repp(i,n,1){ if (i > n - i) break; int a = i; int b = n - i; map<int,int> ima; while (a > 1){ int h = div[a]; if (ima.find(h) == ima.end()) ima[h] = 1; else ima[h]++; a /= h; } while (b > 1){ int h = div[b]; if (ima.find(h) == ima.end()) ima[h] = 1; else ima[h]++; b /= h; } for (auto p : ima){ if (mp.find(p.first) == mp.end()) mp[p.first] = p.second; else chmax(mp[p.first],p.second); } } modint998244353 ans = 1; for (P q : mp){ modint998244353 y = q.first; ans *= y.pow(q.second); } cout << ans.val() << endl; }