結果
問題 | No.2074 Product is Square ? |
ユーザー |
![]() |
提出日時 | 2023-03-03 21:30:05 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 440 ms / 2,000 ms |
コード長 | 1,476 bytes |
コンパイル時間 | 3,370 ms |
コンパイル使用メモリ | 250,164 KB |
最終ジャッジ日時 | 2025-02-11 01:50:24 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using namespace std; using ll=long long; using ld=double; ld pie=3.14159265359; ll mod=998244353; long long inf=100000000000000001; ll gcd(ll a, ll b) { a = abs(a); b = abs(b); if (a < b)swap(a, b); while (b) { ll r=a%b; a=b; b=r; } return a; } int main(){ ll t; cin >> t; for (ll o = 0; o < t; o++) { ll n; cin >> n; vector<ll>a(n); for (ll i = 0; i < n; i++) { cin >> a[i]; } for (ll i = 0; i < n; i++) { for (ll j = i+1; j < n; j++) { ll x=gcd(a[i],a[j]); a[i]/=x; a[j]/=x; } } bool ok=true; for (ll i = 0; i < n; i++) { ll left=0,right=a[i]+1; while (right-left>1) { ll mid=(right+left)/2; ll y=0; if (a[i]%mid>=1) { y=1; } if (mid>a[i]/mid+y) { right=mid; }else{ left=mid; } } if (left*left!=a[i]) { ok=false; } } if (ok) { cout << "Yes" << endl; }else{ cout << "No" << endl; } } }