結果
問題 | No.2074 Product is Square ? |
ユーザー |
👑 |
提出日時 | 2022-09-16 22:57:57 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,169 bytes |
コンパイル時間 | 1,900 ms |
コンパイル使用メモリ | 197,884 KB |
最終ジャッジ日時 | 2025-02-07 10:29:45 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 2 TLE * 31 |
ソースコード
// #define _GLIBCXX_DEBUG#include<bits/stdc++.h>using namespace std;using uint = unsigned int;using ll = long long;#define CIN( LL , A ) LL A; cin >> A#define GETLINE( A ) string A; getline( cin , A )#define GETLINE_SEPARATE( A , SEPARATOR ) string A; getline( cin , A , SEPARATOR )#define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr )#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( ll VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ )#define FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ )#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES )#define RETURN( ANSWER ) cout << ( ANSWER ) << endl; return 0#define DOUBLE( PRECISION , ANSWER ) cout << fixed << setprecision( PRECISION ) << ( ANSWER ) << endl; return 0#define MIN( A , B ) A < B ? A : B;#define MAX( A , B ) A < B ? B : A;template <typename T> inline T Absolute( const T& a ){ return a > 0 ? a : - a; }int main(){CIN( ll , T );constexpr const ll bound = 65536;vector<ll> p{};p.push_back( 2 );ll size = 1;FOR( i , 3 , bound ){bool prime = true;FOR( j , 0 , size ){ll& pj = p[j];if( i % pj == 0 ){prime = false;break;} else if( pj * pj > i ){break;}}if( prime ){p.push_back( i );size++;}i++;}ll prime_back = p[size - 1];REPEAT( T ){CIN( ll , N );vector<ll> count( size );FOR( i , 0 , N ){CIN( ll , Ai );FOR( j , 0 , size ){ll& pj = p[j];if( Ai % pj == 0 ){ll& count_j = count[j];while( Ai % pj == 0 ){Ai /= pj;count_j++;}}}ll p_next = prime_back + 2;while( Ai != 1 ){if( Ai % p_next == 0 ){while( Ai % p_next == 0 ){Ai /= p_next;}p.push_back( p_next );} else if( p_next * p_next > Ai ){p.push_back( Ai );Ai = 1;}p_next += 2;}}bool square = true;FOR( j , 0 , size ){if( count[j] % 2 == 1 ){square = false;break;}}if( square ){cout << "Yes\n";} else {cout << "No\n";}}return 0;}