[Codeforces 1025B] Weakened Common Divisor

[Codeforces 1025B] Weakened Common Divisor - 1600

문제 설명 : 

문제에서 WCD라는 연산을 정의한다. 이 연산은 양의 정수 2개로 구성된 pair가 총 n개 주어질 때 두 수 중에서 최소 1개는 나누어 떨어지는 공약수를 전체 n개의 pair에 대해서 찾을 수 있으면 그 공약수를 구하거나 불가능함을 밝히는 문제이다.

풀이 : 

pair가 최대15만개 주어지므로 숫자는 총 30만개이고 각 수의 최대 범위는 20억이다. naive하게 생각하면 30만개 수를 모두 소인수분해해서 그 수들의 공약수를 찾으면 되는데, 소인수분해 알고리즘의 시간복잡도는 단발성 소인수분해는 O(sqrt(RANGE)), 전처리 소인수분해는 O(N*RANGE*log(log(RANGE)))이다(RANGE는 수의 최대 범위). 이 문제에서는 RANGE=20억이므로 두 알고리즘 모두 사용할 수 없다. 따라서 다른 효율적인 방법이 필요하다. 

그 힌트는 문제에서 찾을 수 있다. 이 문제는 기존의 소인수분해 문제가 아닌, n개의 pair가 주어지고 각 pair의 두 수 중에서 최소 1개로만 나누어 떨어지기만 하면 된다. 즉 전체 n개 pair들의 1이 아닌 공약수가 존재한다면, n개 중 어떤 임의의 pair가 있을 때 그 pair들의 소인수들 중 최소 한개는 다른 (n-1)개의 pair로 나누어 떨어지는게 확실하다. 이런 관점에서 생각하면 조사해야할 범위를 대폭 줄일 수 있다. 어떤 수의 소인수의 최대 개수는 log(RANGE)이고 이를 n개의 수에 대해서 나누어 떨어질 수 있는지 확인하면 되므로 총 시간복잡도는 O(N*log(RANGE))가 된다.

주의할 점 : 

n=1일 때는 소인수분해 할 필요 없이, 두 수 중에서 아무 수나 출력하면 된다.

배울 점 : 

문제의 특성을 생각해서 조사해야할 범위를 크게 줄일 수 있다. 소인수분해 알고리즘은 O(sqrt(RANGE))이지만 소인수의 최대 개수는 log(RANGE)라서 왠만한 범위에서는 소인수의 개수가 더 적기 때문에 조사 범위가 줄었다고 할 수 있다.

코드 :

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<assert.h>
#include<stdlib.h>
#include<stack>
using namespace std;
/*********************Contest Template***********************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<int,int> Cord;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(0);
struct S{
    int a,b;
 
    S(){}
    S(int _a,int _b){
        a=_a;
        b=_b;
    }
 
    const bool operator<(const S &o) const{
        return a<o.a;
    }
};
priority_queue<int,vector<int>,greater<int>> mpq;
#define SPACE 0
#define NL 1
inline void showAll(vector<int> &v,int NL_or_space){ 
    //0 is space, 1 is NL
    for(int &here:v){
        printf("%d",here);
        printf("%c",(NL_or_space)?'\n':' ');
    }
}
/*********************Contest Template***********************/
const int SIZE= 150009;
 
pii arr[SIZE];
 
int main(){
    int n;  scanf("%d",&n);
 
    for(int i=1 ; i<=n ; i++){
        int a,b;    scanf("%d %d",&a,&b);
        arr[i]={a,b};
    }
 
    if(n==1){
        printf("%d",arr[1].first);
        return 0;
    }
 
    set<int> p_fact;
    int k=arr[1].first;
    for(int i=2 ; i*i<=k ; i++){
        while(k%i==0){
            p_fact.insert(i);
            k/=i;
        }
    }
    if(k!=1) p_fact.insert(k);
 
    k=arr[1].second;
    for(int i=2 ; i*i<=k ; i++){
        while(k%i==0){
            p_fact.insert(i);
            k/=i;
        }
    }
    if(k!=1) p_fact.insert(k);
    
    for(int here:p_fact){
        for(int i=2 ; i<=n ; i++){
            if(arr[i].first%here && arr[i].second%here) break;
            if(i==n) {
                printf("%d",here);
                return 0;
            }
        }
    }
    printf("-1\n");
    return 0;
}