結果
問題 | No.2074 Product is Square ? |
ユーザー |
![]() |
提出日時 | 2022-09-16 23:02:03 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 6,099 bytes |
コンパイル時間 | 8,715 ms |
コンパイル使用メモリ | 459,648 KB |
実行使用メモリ | 17,224 KB |
最終ジャッジ日時 | 2024-12-21 22:32:11 |
合計ジャッジ時間 | 103,249 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 2 TLE * 31 |
ソースコード
/*このコード、と~おれ!Be accepted!∧_∧(。・ω・。)つ━☆・*。⊂ ノ ・゜+.しーJ °。+ *´¨).· ´¸.·*´¨) ¸.·*¨)(¸.·´ (¸.·'* ☆*/#include <cstdio>#include <algorithm>#include <string>#include <cmath>#include <cstring>#include <vector>#include <numeric>#include <iostream>#include <random>#include <map>#include <unordered_map>#include <queue>#include <regex>#include <functional>#include <complex>#include <list>#include <cassert>#include <iomanip>#include <set>#include <stack>#include <bitset>#include <array>#include <chrono>//#pragma GCC target("arch=skylake-avx512")//#pragma GCC target("avx2")//#pragma GCC optimize("O3")//#pragma GCC optimize("Ofast")//#pragma GCC target("sse4")//#pragma GCC optimize("unroll-loops")//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")#define repeat(i, n, m) for(int i = n; i < (m); ++i)#define rep(i, n) for(int i = 0; i < (n); ++i)#define printynl(a) printf(a ? "yes\n" : "no\n")#define printyn(a) printf(a ? "Yes\n" : "No\n")#define printYN(a) printf(a ? "YES\n" : "NO\n")#define printim(a) printf(a ? "possible\n" : "imposible\n")#define printdb(a) printf("%.50lf\n", a)#define printLdb(a) printf("%.50Lf\n", a)#define printdbd(a) printf("%.16lf\n", a)#define prints(s) printf("%s\n", s.c_str())#define all(x) (x).begin(), (x).end()#define deg_to_rad(deg) (((deg)/360.0L)*2.0L*PI)#define rad_to_deg(rad) (((rad)/2.0L/PI)*360.0L)#define Please return#define AC 0#define manhattan_dist(a, b, c, d) (abs(a - c) + abs(b - d))using ll = long long;using ull = unsigned long long;constexpr int INF = 1073741823;constexpr int MINF = -1073741823;constexpr ll LINF = ll(4661686018427387903);constexpr ll MOD = 1e9 + 7;constexpr ll mod = 998244353;constexpr long double eps = 1e-14;const long double PI = acosl(-1.0L);using namespace std;void scans(string& str) {char c;str = "";scanf("%c", &c);if (c == '\n')scanf("%c", &c);while (c != '\n' && c != -1 && c != ' ') {str += c;scanf("%c", &c);}}void scanc(char& str) {char c;scanf("%c", &c);if (c == -1)return;while (c == '\n') {scanf("%c", &c);}str = c;}double acot(double x) {return PI / 2 - atan(x);}ll LSB(ll n) { return (n & (-n)); }template<typename T>inline T chmin(T& a, const T& b) {if (a > b)a = b;return a;}template<typename T>inline T chmax(T& a, const T& b) {if (a < b)a = b;return a;}//cpp_int#if __has_include(<boost/multiprecision/cpp_int.hpp>)#include <boost/multiprecision/cpp_int.hpp>#include <boost/multiprecision/cpp_dec_float.hpp>using namespace boost::multiprecision;#elseusing cpp_int = ll;#endif//atcoder library#if __has_include(<atcoder/all>)#include <atcoder/all>//using namespace atcoder;#endif/*random_device seed_gen;mt19937 engine(seed_gen());uniform_int_distribution dist(1, 100);*//*----------------------------------------------------------------------------------*//*The implementation of Rho Method with C++varified with NTL_1_Ahttp://joisino.hatenablog.com/entry/2017/08/03/210000Copyright (c) 2017 joisinoReleased under the MIT licensehttp://opensource.org/licenses/mit-license.php*/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 primebool 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;}};Rho rho;random_device seed_gen;mt19937 engine(seed_gen());uniform_int_distribution dist(1ll, (ll)1e18);int main() {int t;scanf("%d", &t);map<ll, int> hash;while (t--) {int n;scanf("%d", &n);vector<ll> a(n);ll x = 0;rep(i, n) {scanf("%lld", &a[i]);vector<ll> d = rho.factor(a[i]);sort(all(d));for (const auto& aa : d) {if (not hash[aa])hash[aa] = dist(engine);x ^= hash[aa];}}printyn(x == 0);}Please AC;}