#798151 (C++17) No.2074 Product is Square ?

• 問題: No.2074 Product is Square ?
• ユーザー: kwm_t
• 提出日時: 2022-09-16 22:18:34
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: TLE
• 実行時間: -
• コード長: 2,788 bytes
• コンパイル時間: 2,398 ms
• コンパイル使用メモリ: 207,640 KB
• 最終ジャッジ日時: 2025-02-07 09:57:34
• ジャッジサーバーID （参考情報）: judge3 / judge3

ファイルパターン	結果
sample	AC * 1
other	AC * 2 TLE * 31

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;
//using mint = modint1000000007;
//const int mod = 1000000007;
//using mint = modint998244353;
//const int mod = 998244353;
//const int INF = 1e9;
//const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i,l,r)for(int i=(l);i<(r);++i)
#define rrep(i, n) for (int i = (n-1); i >= 0; --i)
#define rrep2(i,l,r)for(int i=(r-1);i>=(l);--i)
#define all(x) (x).begin(),(x).end()
#define allR(x) (x).rbegin(),(x).rend()
#define endl "\n"
#define P pair<int,int>
template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }
struct Miller {
    const vector<long long> v = { 2 , 7 , 61 }; // < 4,759,123,141
    // x^k (mod m)
    long long modpow(long long x, long long k, long long m) {
        long long res = 1;
        while (k) {
            if (k & 1) {
                res = res * x % m;
            }
            k /= 2;
            x = x * x % m;
        }
        return res;
    }
    // check if n is prime
    bool check(long long n) {
        if (n < 2) {
            return false;
        }
        long long d = n - 1;
        long long s = 0;
        while (d % 2 == 0) {
            d /= 2;
            s++;
        }
        for (long long a : v) {
            if (a == n) {
                return true;
            }
            if (modpow(a, d, n) != 1) {
                bool ok = true;
                for (long long r = 0; r < s; r++) {
                    if (modpow(a, d * (1LL << r), n) == n - 1) {
                        ok = false;
                        break;
                    }
                }
                if (ok) {
                    return false;
                }
            }
        }
        return true;
    }
};
struct Rho {
    mt19937 mt;
    Miller miller;
    long long c;
    Rho() {
        mt.seed(clock());
    }
    inline long long f(long long x, long long n) {
        return (x * x + c) % n;
    }
    long long check(long long n) {
        if (n == 4) {
            return 2;
        }
        c = mt() % n;
        long long x = mt() % n;
        long long y = x;
        long long d = 1;
        while (d == 1) {
            x = f(x, n);
            y = f(f(y, n), n);
            d = gcd(abs(x - y), n);
        }
        if (d == n) {
            return -1;
        }
        return d;
    }
    vector<long long> factor(long long n) {
        if (n <= 1) {
            return {};
        }
        if (miller.check(n)) {
            return { n };
        }
        long long res = -1;
        while (res == -1) {
            res = check(n);
        }
        vector<long long> fa = factor(res);
        vector<long long> fb = factor(n / res);
        fa.insert(fa.end(), fb.begin(), fb.end());
        return fa;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Rho rho;
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        map<long long, int>mp;
        rep(i, n) {
            long long a; cin >> a;
            auto v = rho.factor(a);
            for (auto e : v)mp[e]++;
        }
        bool chk = true;
        for (auto[k, v] : mp)if (1 == v % 2)chk = false;
        if (chk)cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX