結果
問題 | No.1396 Giri |
ユーザー |
![]() |
提出日時 | 2021-02-11 16:31:52 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 31 ms / 2,000 ms |
コード長 | 599 bytes |
コンパイル時間 | 742 ms |
コンパイル使用メモリ | 66,816 KB |
最終ジャッジ日時 | 2025-01-18 17:33:12 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include<iostream> using namespace std; typedef long long lint; #define rep(i,n)for(int i=0;i<(int)(n);++i) const int N=1e6+10; bool pr[N],pp[N]; int fac[N]; void pr_init(void){ rep(i,N)if(i>=2)pr[i]=1; rep(i,N){ if(i<=1)continue; if(!pr[i])continue; fac[i]=i; pp[i]=1; for(lint j=lint(i)*i;j<N;j+=i){ pr[j]=0; if(fac[j]==0)fac[j]=i,pp[j]=pp[j/i]&&fac[j/i]==i; } } } int main(){ int n;cin>>n; pr_init(); lint p=0; rep(i,n+1)if(pr[i])p=i; lint ans=1; for(lint i=1;i<=n;i++){ if(i!=p&&pp[i])ans=ans*fac[i]%998244353; } cout<<ans<<endl; }