1561번: 놀이 공원

https://www.acmicpc.net/problem/1561


$O(mlgL)$ // L: 탐색 구간 크기

t=0, 1, ... 증가하면서
t%a[i]==0인 i번 놀이 기구를 탄다고 하자.

f(x)를 t=x일 때까지 놀이 기구를 탄 횟수라고 하자.
즉, f(x)=sum(x/s[i])

그러면 n번 아이가 t=a에 놀이 기구를 탔다면
x>=a인 모든 x에 대해 f(x)>=n이고,
x<a인 모든 x에 대해 f(x)<n일 것이다.

이제 파라매트릭 서치를 할 수 있다.

#include<cstdio>
typedef long long ll;
int n, m, a[10000];
ll f(ll x) {
    ll s = 0;
    for (int i = 0; i < m; i++) s += x / a[i];
    return s;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) scanf("%d", a + i);
    ll low = 1, up = 6e10, mid;
    n -= m;
    while (low <= up) {
        mid = (low + up) / 2;
        f(mid) >= n ? up = mid - 1 : low = mid + 1;
    }
    int c = f(low) - n;
    for (int i = m; i--;) if (low%a[i] == 0 && !c--) {
        printf("%d", i + 1);
        break;
    }
    return 0;
}