codeforce 1600

COFO::1771C Hossam and Trainees

cofo problem

COFO::1771C Hossam and Trainees

Problem

Point

Design

Thought process

open/close 
x >= 2 이면 되므로,
원소 중에 짝수가 2개 이상 있으면 무조건 YES

문제는, 
. 짝수가 1개 있고 모두 홀수 이거나
. 모두 홀수인 경우


* naive 하게는, O(N^2) 으로
두 원소를 선택해서 GCD 를 구해보는 것. ( >= 2)


* Eratosthenes
for (int i = 2; i * i <= n; i++) {
	if (n % i) {
		push_back(i);
		if (n/i != i) {
			push_back(n/i);
		}
	}
}

===========================================

* 방법 1.
각 원소의 모든 약수를 구해보는게 어떨까?
그리고 이 약수가 하나라도 겹치는게 있으면 YES?
-----
약수가 겹친다는건 GCD 로 1이 아닌 원소를 갖는다는 것이니까

-> 너무 간단하다 싶었더니 TLE 임
n = 1e5 이고, a[i] = 1e9 니까, 에라토스 쓰더라도 복잡도가

1e5 * 1e(4.5) = 1e(9.5) 가 되어서 TLE 가 됨.
	- 에라토스를 3부터 i += 2 씩 해도 안됨.
===========================================

* 방법 2.
모든 원소를 곱하고,,
- 제곱수를 찾는다?
-> root(1e14) = 1e7 이라 충분해지긴 함.

근데 하나의 수에서 제곱수가 나오는 경우도 있을 수 있음;;
2 * 3^2 = 18 
3^2 * 5^2 = 225 


============================================

* 방법 3.
모든 원소의 최소 공배수를 구한다.
이 값이 모든 원소의 곱보다 작으면 YES
. 예를들어 5 7 25 가 있다고 하자.
  . A = LCM(5, 7, 25) = LCM(7, 25) = 7 * 25 = 175 
  . B = 5 * 7 * 25 = 875 
 . 5 와 25 의 최대 공약수가 5이므로, 둘의 최소 공배수는 25가 된다.

아 근데 모든 수의 곱이 무조건 overflow 네
(10^9)^(10^5) 이네

이 방법이 맞을 것 같은데, overflow 를 우회해갈 방법이 없나?
-> 전체 수의 최소 공배수를 구하고 이를 X 라고 하자.
-> 그리고 각 원소를 순회하면서,
   Y = X / a[i] 를 한다. ( a[i] 를 X 에서 제외하는 것 )
  그리고 GCD(Y, a[i]) 가 2이상인지 확인한다.

근데 LCM 구할때 overflow 발생하는듯. 왜지?

Complexity

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for(int i = (a); i <(b); i++)
#define r_rep(i, a, b) for(int i = (a); i >(b); i--)
typedef long long ll;
using namespace std;
const ll N = 1e5 + 9;

int cur;
bool ans;
bool isPrime[N];
int visited[N];
vector<int> primes;
map<int,int> mp;
void preCalc() {
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = isPrime[1] = false;
    for(int i = 2; i * i < N; i++) {
        if (!isPrime[i]) continue;
        for(int j = i + i; j < N; j += i)
            isPrime[j] = false;
    }
    
    for(int i = 2; i < N; i++)
        if (isPrime[i]) primes.push_back(i);
}
void check(int x) {
    if (visited[x] == cur) {
        ans = true;
        return;
    }
    visited[x] = cur;
}
void fact(int x) {
    if (x < N && isPrime[x] == true) {
        check(x);
        return;
    }
    
    int pos = 0, sz = sz(primes);
    while(x > 1 && pos < sz && x / primes[pos] >= primes[pos]) {
        if (x % primes[pos] == 0) {
            check(primes[pos]);
            while(x % primes[pos] == 0) x /= primes[pos];
        }
        pos ++;
    }
    if (x > 1) {
        if (x < N) return check(x), void();
        if (mp.find(x) != mp.end()) {
            ans = true;
        } else {
            mp[x] = 1;
        }
    }
}
void solve() {
    mp.clear();
    ans = false;
    cur++;
    int n; cin >> n;
    while(n--) {
        int x; cin >> x;
        fact(x);
    }
    if (ans) cout << "YES\n";
    else cout << "NO\n";
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    preCalc();
    int tc; cin >> tc; while(tc--)
        solve();
    return 0;
}