結果

問題 No.2074 Product is Square ?
ユーザー みここ
提出日時 2022-12-13 00:47:38
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,848 ms / 2,000 ms
コード長 2,218 bytes
コンパイル時間 914 ms
コンパイル使用メモリ 75,632 KB
最終ジャッジ日時 2025-02-09 10:44:18
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
long long gcd(long long n, long long m)
{
if (m == 0)
{
return n;
}
return gcd(m, n % m);
}
std::vector<int> enum_prime(int n) // containing n
{
std::vector<int> res;
if (n <= 1)
{
return res;
}
std::vector<bool> p(n + 1);
fill(p.begin() + 2, p.end(), true);
for (int i = 2; i <= n; i++)
{
if (p[i])
{
res.push_back(i);
for (int j = i * 2; j <= n; j += i)
{
p[j] = false;
}
}
}
return res;
}
bool is_square(ll x)
{
ll left = -1, right = 1000000001;
while (right - left > 1)
{
ll mid = (right + left) / 2;
if (mid * mid >= x)
{
right = mid;
}
else
{
left = mid;
}
}
return right * right == x;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
vector<int> prime = enum_prime(1000000);
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
bool b[1000005]{0};
ll a[1005];
for (int i = 0; i < n; i++)
{
cin >> a[i];
for (int p : prime)
{
if (a[i] % p == 0)
{
while (a[i] % ((ll)p * p) == 0)
{
a[i] /= p * p;
}
if (a[i] % p == 0)
{
a[i] /= p;
b[p] ^= 1;
}
}
}
if (is_square(a[i]))
{
a[i] = 1;
}
}
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
ll g = gcd(a[i], a[j]);
a[i] /= g;
a[j] /= g;
}
}
bool f = false;
for (int p : prime)
{
f |= b[p];
}
for (int i = 0; i < n; i++)
{
f |= (a[i] > 1);
}
cout << (!f ? "Yes\n" : "No\n");
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0