Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

A. Perfectly Imperfect Array (Codeforces Round #716 (Div. 2))

問題

https://codeforces.com/contest/1514/problem/A

問題概要

長さnの配列aが与えられる。aの空でない部分配列をbとするとき、すべての要素の積が平方数にならないようなbが存在するかどうかを答えよ。

考察

aの中で、1つでも平方数でないものが含まれている場合、その1つだけを要素としたbを作ればいいので構築可能です。

一方、平方数と平方数の積はx^2 * y^2 = (x * y)^2でやはり平方数になるため、1つも平方数でないものが含まれていない場合どこをどう切り取っても積は平方数にしかならず、構築不可能です。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        // 10000までの平方数をあらかじめ作っておく
        set<int> s;
        for (int i = 1; i <= 100; i++) s.emplace(i * i);
        int a;
        bool ok = false;
        for (int i = 0; i < n; i++) {
            cin >> a;
            if (s.count(a) == 0) ok = true;
        }
        cout << (ok ? "YES" : "NO") << endl;
    }
}