結果
問題 |
No.1529 Constant Lcm
|
ユーザー |
![]() |
提出日時 | 2021-06-04 21:37:36 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,742 bytes |
コンパイル時間 | 2,027 ms |
コンパイル使用メモリ | 175,672 KB |
実行使用メモリ | 706,444 KB |
最終ジャッジ日時 | 2024-11-19 13:11:17 |
合計ジャッジ時間 | 18,628 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 1 |
other | AC * 10 WA * 6 MLE * 8 |
ソースコード
#include <bits/stdc++.h> using namespace std; //#include <atcoder/all> //using namespace atcoder; using ll=long long; using Graph=vector<vector<int>>; #define MAX 1000 #define INF 1000000000000000000 #define MOD 998244353 vector<int> p; vector<bool> p_table(MAX+1,true); void prime(){ p_table.at(0)=false,p_table.at(1)=false; for(int i=2;i<=MAX;i++){ if(p_table.at(i)){ p.push_back(i); for(int j=2;i*j<=MAX;j++){ p_table.at(i*j)=false; } } } } int main(){ int N; cin>>N; prime(); int n=p.size(); vector<vector<int>> cnt(N,vector<int>(n,0)); vector<int> other_p(N,0); for(int i=1;i<N;i++){ int x=i; for(int j=0;j<n;j++){ while(x%p[j]==0){ cnt[i][j]++; x/=p[j]; } } if(x>1){ other_p[i]=x; } } vector<int> max_cnt(n,0); vector<int> other_primes(N,0); for(int i=1;i<N/2;i++){ int x=i; int y=N-i; for(int j=0;j<n;j++){ max_cnt[j]=max(max_cnt[j],cnt[x][j]+cnt[y][j]); } if(other_p[x]==0&&other_p[y]>0){ other_primes[other_p[y]]=max(other_primes[other_p[y]],1); }else if(other_p[x]>0&&other_p[y]==0){ other_primes[other_p[x]]=max(other_primes[other_p[x]],1); }else if(other_p[x]>0&&other_p[y]>0&&other_p[x]!=other_p[y]){ other_primes[other_p[y]]=max(other_primes[other_p[y]],1); other_primes[other_p[x]]=max(other_primes[other_p[x]],1); }else if(other_p[x]>0&&other_p[y]>0){ other_primes[other_p[x]]=2; } } ll ans=1; for(int i=0;i<n;i++){ for(int j=0;j<max_cnt[i];j++){ ans*=(ll)p[i]; ans%=MOD; } } for(int i=1;i<=N;i++){ for(int j=0;j<other_primes[i];j++){ ans*=(ll)i; ans%=MOD; } } cout<<ans<<endl; }