[Codeforces 1034A] Enlarge GCD

[Codeforces 1034A] Enlarge GCD - 1700

문제 설명 : 

n개의 숫자가 주어진다. 이 중에서 숫자 k 개를 삭제한 뒤 나머지 (n-k)개 수들의  GCD(최대공약수)가 삭제하기 이전의 GCD보다 크도록 만들어야 한다. 그러기 위해서는 최소 몇 개의 숫자를 삭제해야 하는지 구하는 문제이다(= 가장 작은 k값을 구하여라).

풀이 : 

먼저 N개 수들의 GCD를 먼저 구한 뒤, 다시 모든 수들을 GCD로 나눠준다. 나눠진 수들의 GCD는 당연히 1이다. 이 숫자들을 각각 소인수분해하여 가장 많이 등장하는 소인수의 횟수를 N에서 빼주면 된다. 가장 많이 등장하는 소인수를 포함하지 않은 수들을 모두 삭제하고 나면, 그 소인수를 GCD로 취할 수 있기 때문이다. 

그리고 이 문제에서 중요한 issue가 되는 것이 소인수분해이다. for문안에 while문을 넣는 소인수분해 방법은 크기가 RANGE인 수 하나를 소인수분해 하는데 시간이 O(sqrt(RANGE))만큼 소모된다. 따라서 이 문제에서 수의 범위가 최대 1500만이고 개수는 30만개이므로 O( sqrt(1500만) * 30만 )을 하면 10억이 훌쩍 넘어간다. 따라서 소인수분해를 다른 방법으로 해야한다. 이에 대한 방법은 마침 얼마 전에 reference로 작성했었던 소인수분해에 나와있다. 복습을 다시 해보자면 에라토스테네스의 체를 변형하여 1~RANGE까지의 모든 수에 대하여 해당 숫자가 가지는 가장 작은 인수를 저장하는 전처리 과정을 거친다. 이 알고리즘의 시간복잡도는 O( RANGE * log(log(RANGE) )이다. RANGE=1500만을 대입해보면 정말 아슬아슬하게 5000만 정도이다. 아무튼 첫 번째 소인수분해 방법보다는 빠르니 이 방법을 사용해야 한다는 것은 확실하다.

주의할 점 : 

위 풀이로 제출하면 1초 제한에 무려 997ms가 나온다. 소인수분해 과정에서 걸리는 cost가 거의 대부분이다. 다른 사람들의 코드를 보니 더 최적화를 거쳐서 600ms까지 줄이기는 하는데 나는 거기까지의 최적화는 잘 모르겠다. 다만 이 풀이가 정해인 것은 확실한데 시간이 너무 촉박한 걸 보니 문제에 논란의 여지가 있기는 하다.

배운 점 : 

오랜만에 GCD구하는 코드를 remind했다. 

소인수분해를 해야할 숫자가 많아지면 에라토스테네스의 체를 이용한 방법을 사용하자.

코드 : 

#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;
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= 3000009;
const int RANGE=15000009;
int arr[SIZE];
int minfact[RANGE];
map<int,int> after;
int getGCD(int a,int b){
    return (b==0)? a : getGCD(b,a%b);
}
 
int main(){
    int n;  scanf("%d",&n);
    int G;
    for(int i=1 ; i<=n ; i++){
        scanf("%d",&arr[i]);
        if(i==1) G=arr[i];
        else G=getGCD(G,arr[i]);
    }
 
    for(int i=2 ; i<RANGE ; i++)
        minfact[i]=i;
    for(int i=2 ; i*i<RANGE ; i++){
        for(int j=i*i ; j<RANGE ; j+=i){
            if(minfact[j]==j){
                minfact[j]=i;
            }
        }
    }
 
    for(int i=1 ; i<=n ; i++){
        arr[i]/=G;
        set<int> tmp;
        while(arr[i]>1){
            tmp.insert(minfact[arr[i]]);
            arr[i]/=minfact[arr[i]];
        }
        for(int here:tmp)
            after[here]++;
    }
    int max_cnt=0;
    for(auto here:after){
        max_cnt=max(max_cnt,here.second);
    }
    if(max_cnt==0) printf("-1\n");
    else printf("%d\n",n-max_cnt);
    return 0;
}