BOJ 15907 - Acka의 리듬 세상

문제 링크 : https://www.acmicpc.net/problem/15907

문제 설명

n개의 수들 중에서 최대한 많은 수를 포함하는 ax+b (a는 2이상의 정수, b,x 는 정수) 꼴을 찾아내야 한다. 이때 그 꼴으로 표현할 수 있는 수의 갯수를 출력하면 된다. 

문제 풀이

ax+b 꼴에 최대한 많은 수를 포함시켜야 한다. 생각을 해보자. 2로 나눈 나머지로 수들을 분리하는것이 무조건 4,6,8,10..등으로 수를 분리하는 것보다 이득이다. 이는 3,4,5... 등에 대해서도 모두 적용되는 논리이다. i로 분리해서 확인하면 ki꼴의 수에 대해서는 확인하지 않는 것이 이득이다. 이러면 무엇이 떠오르는가? 당연히 소수이다. 즉, 소수에 대해서만 판별을 하면 된다는 것이다.

2000000만까지의 모든 소수를 구한 다음에 어떤 소수로 나눈 나머지가 최대한 많이 겹치는 것을 모두 돌리면서 찾아보면 된다. 소수당 $O(N)$이다. 근데 이러면 2000000까지의 소수의 개수 * 1000이 되고, 시간안에 동작을 하지 않는다. 

아이디어를 하나 생각하자. a가 과연 2000000까지 필요한가에 대해서 이다. 2000000으로 나눈 나머지는 모두 다를것이다. 당연히 선택될 일이 전혀 없다. 임의의 두 점은 한 직선 위에 놓을 수 있기 때문에 최소값은 2가 된다. 따라서 1000000까지만 생각을 해도 된다.

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
vector<ll> pri;
ll com[2020202];
ll arr[1010101];
ll cnt[2020202];
ll sn;
bool sf(ll a,ll b){
    return a%sn<b%sn;
}
 
int main(){
    ll i,j,k,l,m,n;
    scanf("%lld",&n);
    for(i=1;i<=n;i++)
        scanf("%lld",&arr[i]);
    for(i=2;i<=1000000;i++){
        if(!com[i]) pri.push_back(i);
        for(j=0;j<pri.size()&&i*pri[j]<1000000;j++){
            com[i * pri[j]] = 1;
            if (i % pri[j] == 0) break;
        }
    }    
 
    ll ans=0;
    for(auto k:pri){
        sn=k;
        for(i=1;i<=n;i++){
            cnt[arr[i]%k]++;
            ans=max(ans,cnt[arr[i]%k]);
        }
        for(i=1;i<=n;i++){
            cnt[arr[i]%k]--;
        }
    }
 
    printf("%lld",ans);
 
}