結果
問題 |
No.2379 Burnside's Theorem
|
ユーザー |
|
提出日時 | 2023-07-14 21:30:55 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 55 ms / 2,000 ms |
コード長 | 1,192 bytes |
コンパイル時間 | 2,020 ms |
コンパイル使用メモリ | 216,808 KB |
最終ジャッジ日時 | 2025-02-15 10:42:31 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 20 |
ソースコード
#include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #define go(); ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define all(v) v.begin(),v.end() #define rall(v) v.rbegin(),v.rend() #define debug(x) cout<<#x<<" "<<x<<endl; using namespace std; using namespace __gnu_pbds; template<typename T> using ordered_set=tree <T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; typedef long long ll; typedef long double ld; const ll mod=1e9+7; const ll mxn=2e5+3; const ll inf=1e18; vector<ll>p,c(2000000+10,0); void seive() { for(ll i=2;i<=2000000;i++) { if(c[i]) continue; p.push_back(i); for(ll j=i*i;j<=200000;j+=i) { c[j]=1; } } } void solve() { ll n; cin>>n; ll c=0; if(n==1) { cout<<"Yes\n"; return; } seive(); for(int i=0;i<p.size();i++) { if(n%p[i]==0) { c++; // debug(p[i]); while(n%p[i]==0) { n/=p[i]; } } } if(n>1) c++; if(c==2||c==1) { cout<<"Yes\n"; } else cout<<"No\n"; } int main() { go(); ll t=1; // cin>>t; while(t--) { solve(); } return 0; }