C. Hossam and Trainees
太久没登博客园了密码都忘记了...
题目大意
给n个数，问能不能找到一个x使得x整除其中的任意两个数。
思路
这题的解法很快就想出来了，就是直接每个数字拆分质因子。我们可以通过筛法将sqrt(1e9)内的所有质数预处理出来即可。
赛时没做出来是因为这题卡了unordered_map，只能说血亏
ll prm[N] , cnt ;
ll st[N] ;
ll m ;
void euler(ll n){
m = sqrt(n) + 10 ;// cout << m << "\n" ;
for(ll i = 2 ; i <= m ; i ++ ){
// cout << i << "<\n" ;
if(!st[i]){
prm[ ++ cnt] = i ;
}
for(ll j = 1 ; j <= cnt && prm[j]*i <= m ; j ++ ){
st[prm[j]*i] = 1 ;
if(i % prm[j] == 0) break ;
}
}
}
string solve(){
ll n ; cin >> n ;
vct<ll> a(n + 1 , 0) ;
rep(i , 1 , n) cin >> a[i] ;
map<ll , int> vs ;
rep(i , 1 , n){
ll tmp = a[i] ;
for(int j = 1 ; j <= cnt && prm[j] <= tmp ; j ++ ){
if(a[i] % prm[j] == 0){//cout << prm[j] << " " ;
if( ++ vs[prm[j]] == 2) return "YES\n" ;
while(a[i] % prm[j] == 0) a[i] /= prm[j] ;
}
}
if(a[i] > 1)
if( ++ vs[a[i]] == 2) return "YES\n" ;
}
return "NO\n" ;
}//code_by_tyrii
int main(){
euler(1e9 + 10) ;
// freopen("in.in" , "r" , stdin) ;
// freopen("out.out" , "w" , stdout) ;
ios::sync_with_stdio(false) ;
cin.tie(0) ; cout.tie(0) ;
ll T ; cin >> T ;
while(T -- )
cout << solve() ;
}