# CSES [Factory Machines](https://cses.fi/problemset/task/1620/) 題解
[TOC]
## 題目大意
給定$n$、$t$、$k_1,k_2,\dots,k_n$，求最小的$x$使得$\sum_{i=1}^{n}\lfloor \frac{x}{k_i}\rfloor\geq t$
- $1 \le n \le 2 \cdot 10^5$
- $1 \le t \le 10^9$
- $1 \le k_i \le 10^9$
## 範例測資
input:

3 7
3 2 5

ouput:

8

## 觀察
$x$越大，$\sum_{i=1}^{n}\lfloor \frac{x}{k_i}\rfloor$越大，反之亦然。
以範測為例:
|$x$|1|2|3|4|5|6|7|8|9|10|
|---|---|---|---|---|---|---|---|---|---|---|
|$\sum_{i=1}^{n}\lfloor \frac{x}{k_i}\rfloor$|0|1|2|3|4|6|6|7|8|10|

因為我們只在乎它有沒有大於$t$，所以可以轉換如下:
|$x$|1|2|3|4|5|6|7|8|9|10|
|---|---|---|---|---|---|---|---|---|---|---|
|是否大於等於$t$|0|0|0|0|0|0|0|1|1|1|

存在單調性，因此可以使用**二分搜**。
## 實作
可以使用變數$l$作為左界，表示目前最大的**不可能為答案的數**；變數$r$為右界，表示目前最小的**可能為答案的數**。
每次檢查$\text{mid}=\frac{l+r}{2}$是否可能為答案，並更新左界或右界，直到$r=l+1$為止，此時的$r$就是答案。
## code

#include<bits/stdc++.h>
#define ll long long //將程式碼中的ll替換為long long
using namespace std;
ll n,t;
vector<ll> k;
bool check(ll x){ //檢查x是否有可能是答案
    ll temp=0;
    for(int i=0;i<n;i++){
        temp+=x/k[i];
        if(temp>=t) return 1;
        //為避免溢位，發現有可能是答案時就直接回傳
    }
    return 0;
}
int main(){
    cin>>n>>t;
    k.resize(n);
    for(int i=0;i<n;i++){
        cin>>k[i];
    }
    ll l=0,r=1e18,mid; //1e18=1*10^18
    /*根據題目範圍發現，check(0)一定為0，check(1e18)一定為1，
     因此選擇這兩個數作為一開始的左界和右界*/
    while(r-l>1){ //做到r==l+1為止
        mid=(l+r)/2;
        if(check(mid)) r=mid; //mid有可能是答案，更新右界。
        else l=mid; //mid不可能是答案，更新左界
    }
    cout<<r<<endl;
    return 0;
}

## 複雜度分析
每次把左、右界的距離減半，直到距離為1，因此共需檢查$\log_{2}(1e18)$個數字。
每次檢查數字最差都需要把整個$k$跑過一遍，要花$\text{O}(n)$的時間
總時間複雜度約為$\text{O}(n\log_{2}(1e18))$
:::info
若$a^b=c$，且$a,c>0,a\neq 1$，則$b=\log_{a} c$
:::