結果
問題 |
No.2751 429-like Number
|
ユーザー |
|
提出日時 | 2024-08-18 22:54:28 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,225 ms / 4,000 ms |
コード長 | 1,843 bytes |
コンパイル時間 | 1,474 ms |
コンパイル使用メモリ | 122,104 KB |
最終ジャッジ日時 | 2025-02-23 23:09:07 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 6 |
other | AC * 22 |
ソースコード
#include<iostream> #include<string> #include<queue> #include<vector> #include<cassert> #include<random> #include<set> #include<map> #include<cassert> #include<unordered_map> #include<bitset> #include<numeric> #include<algorithm> using namespace std; typedef long long ll; const int inf=1<<30; const ll INF=1LL<<62; typedef pair<int,ll> P; typedef pair<int,P> PP; const ll MOD=998244353; const int MAXN=100000; vector<bool> is_prime(MAXN+1,true); set<ll> st; vector<ll> prime_list; void init(){ is_prime[0]=is_prime[1]=false; for(int p=2;p<=MAXN;p++){ if(is_prime[p]){ prime_list.push_back(p); for(int j=2*p;j<=MAXN;j+=p){ is_prime[j]=false; } } } // cout<<"prime_list.size():"<<prime_list.size()<<endl; // for(int i=0;i<prime_list.size();i++){ // for(int j=i;j<prime_list.size();j++){ // st.insert(prime_list[i]*prime_list[j]); // } // } } bool solve(){ ll N; cin>>N; bool ok=false; for(ll d=2;d*d*d<=N;d++){ if(N%d==0){ ok=true; break; } } if(!ok)return false; ll c_sum=0; vector<pair<ll,ll>> div; for(ll d=2;d*d<=N;d++){ if(N%d==0){ ll c=0; while(N%d==0){ c++; N/=d; } c_sum+=c; if(c_sum>3) return false; div.push_back({d,c}); } } if(N>1){ c_sum++; div.push_back({N,1}); } if(c_sum>3){ return false; } return c_sum==3; } int main(){ int Q; cin>>Q; //init(); vector<bool> ans(Q); for(int q=0;q<Q;q++){ ans[q]=solve(); } for(int q=0;q<Q;q++){ cout<<(ans[q]?"Yes":"No")<<endl; } }