結果
問題 | No.2074 Product is Square ? |
ユーザー |
![]() |
提出日時 | 2024-03-10 09:58:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 517 ms / 2,000 ms |
コード長 | 1,463 bytes |
コンパイル時間 | 1,412 ms |
コンパイル使用メモリ | 127,968 KB |
最終ジャッジ日時 | 2025-02-20 03:37:21 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 33 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <array> #include <iterator> #include <string> #include <cctype> #include <cstring> #include <cstdlib> #include <cassert> #include <cmath> #include <ctime> #include <iomanip> #include <numeric> #include <stack> #include <queue> #include <map> #include <unordered_map> #include <set> #include <unordered_set> #include <bitset> #include <random> #include <utility> #include <functional> using namespace std; template<class T = long long> T gcd(T a,T b) { while(b) { a %= b; swap(a,b); } return a; } template<class T = long long> T lcm(T a,T b) { return a / gcd<T>(a,b) * b; } void Main() { int N; cin >> N; vector<long long> A(N); for(int i = 0;i < N;i++) { cin >> A[i]; } for(int i = 0;i < N;i++) { for(int j = i + 1;j < N;j++) { long long g = gcd(A[i],A[j]); A[i] /= g; A[j] /= g; } } sort(A.begin(),A.end()); auto sq = [](long long x) -> bool { long long ok = 0,ng = (long long)1e9 + 1; while(ng - ok > 1) { long long mid = (ok + ng) / 2; if(mid * mid <= x) { ok = mid; } else { ng = mid; } } return ok * ok == x; }; for(int i = 0;i < N;) { int j = i; while(j < N && A[j] == A[i]) { j++; } if(!sq(A[i]) && (j - i) & 1) { cout << "No\n"; return; } i = j; } cout << "Yes\n"; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int tt = 1; cin >> tt; while(tt--) Main(); }