题解：P15528 [ROIR 2015 Day 2] forest 伐木
zjd2013
·
·
题解
link
Solution
如果第 $i$ 天砍完了，第 $i + 1$ 天也砍完了；如果第 $i$ 天砍不完，第 $i - 1$ 天也砍不完。有单调性，所以考虑二分。
第 $i$ 天，德米特里砍了 $(i - \lfloor \frac{i}{k} \rfloor) \times a$ 棵树，费多尔砍了 $(i - \lfloor \frac{i}{m} \rfloor) \times b$ 颗。把这两个数加起来，如果大于等于 $x$，那么砍完了，否则没有。
对于一些测试点，二分 check 时会遇到超过 long long 范围上限的数，要用 __int128。
# Code
:::success[code]
```
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef char ch;
typedef string str;
typedef double db;
typedef __int128 i128;
const ll inf=9e18;
const i128 Inf=1e35;
ll a,k,b,m,x,ans;
bool check(i128 d)
{
i128 y=(d-d/k)*a,z=(d-d/m)*b;
return y+z>=x;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>a>>k>>b>>m>>x;
ll l=1,r=1e18,mid;
while(l<=r)
{
mid=(l+r)/2;
if(check(i128(mid))) r=mid-1,ans=mid;
else l=mid+1;
}
cout<<ans;
}
```
:::