結果
問題 | No.2074 Product is Square ? |
ユーザー |
👑 ![]() |
提出日時 | 2022-09-14 20:14:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 492 ms / 2,000 ms |
コード長 | 1,281 bytes |
コンパイル時間 | 680 ms |
コンパイル使用メモリ | 75,792 KB |
最終ジャッジ日時 | 2025-02-07 05:22:02 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 33 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> using namespace std; typedef long long ll; ll my_gcd(ll a, ll b){ ll ret; if (a < b){ swap(a, b); } if (b == 0){ ret = a; } else{ ret = my_gcd(b, a % b); } return ret; } bool is_square(ll a){ ll left = 0; ll right = 1000000001; bool ret = false; while(right - left > 1){ ll center = (left + right) / 2; if (center * center == a){ ret = true; break; } else if (center * center > a){ right = center; } else{ left = center; } } return ret; } int main(){ int T; cin >> T; while(T--){ int N; cin >> N; vector<ll> 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++){ ll g = my_gcd(A[i], A[j]); A[i] /= g; A[j] /= g; } } bool square = true; for (int i = 0; i < N; i++){ if (!is_square(A[i])) square = false; } if (square) cout << "Yes" << endl; else cout << "No" << endl; } }