結果
問題 | No.2074 Product is Square ? |
ユーザー |
![]() |
提出日時 | 2022-09-17 14:27:41 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 881 ms / 2,000 ms |
コード長 | 2,143 bytes |
コンパイル時間 | 2,126 ms |
コンパイル使用メモリ | 210,028 KB |
最終ジャッジ日時 | 2025-02-07 11:19:56 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 33 |
ソースコード
#define rep(i,n) for(int i=0;i<(int)(n);i++)#define ALL(v) v.begin(),v.end()typedef long long ll;#include <bits/stdc++.h>using namespace std;struct Eratosthenes{vector<bool> isprime;vector<int> minfactor;vector<int> mobius;Eratosthenes(int N) : isprime(N+1,true),minfactor(N+1,-1),mobius(N+1,1){isprime[1]=false;minfactor[1]=1;for(int p=2;p<=N;++p){if(!isprime[p]) continue;minfactor[p]=p;mobius[p]=-1;for(int q=p*2;q<=N;q+=p){isprime[q]=false;if(minfactor[q]==-1) minfactor[q]=p;if((q/p)%p==0) mobius[q]=0;else mobius[q]=-mobius[q];}}}vector<pair<int,int>> factorize(int n){vector<pair<int,int>> res;while(n>1){int p=minfactor[n];int exp=0;while(minfactor[n]==p){n/=p;++exp;}res.emplace_back(p, exp);}return res;}vector<int> divisors(int n){vector<int> res({1});auto pf=factorize(n);for(auto p:pf){int s=(int)res.size();for(int i=0;i<s;++i){int v=1;for(int j=0;j<p.second;++j){v*=p.first;res.push_back(res[i]*v);}}}return res;}};int main(){ios::sync_with_stdio(false);std::cin.tie(nullptr);Eratosthenes er(10000);vector<int> B;for(int i=3;i<10000;i++){if(er.isprime[i]) B.push_back(i);}int a=B.size();vector<set<int>> C(a);rep(i,a){int j=0;while(C[i].size()<(B[i]+1)/2){C[i].insert(j*j%B[i]);j++;}}int t;cin>>t;while(t--){int n;cin>>n;vector<ll> A(n);ll cnt=0;rep(i,n){cin>>A[i];while(A[i]%2==0){A[i]/=2;cnt++;}}if(cnt%2==1){cout<<"No"<<endl;continue;}bool b=true;rep(i,a){ll tmp=1;rep(j,n) tmp=tmp*(A[j]%B[i])%B[i];if(C[i].count(tmp)==0) b=false;}if(b) cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;}