这是一篇最后编辑于 8 年前 的文章，其内容可能与目前实际情况差异较大，请注意甄别
题目
{% fold 点击显/隐题目 %}
lls上体育课遇到一个朋友，这个人很会说故事，而且都是神话故事。 这一天lls想听故事了，于是找到了这个朋友，朋友说了一个故事： 很久很久以前…有一个皇帝，他很富有，有很多很多稻米，并且让许多建筑家一起建筑了一个粮仓，专门用来盛放稻谷，容量是n粒稻米，已经装满了。让建筑家没想到的是，稻米是好东西，鸟儿也喜欢吃。为了让皇帝满意，每天早上会有人固定向里面加m粒稻谷(但不能超过容量)。而每天晚上会有鸟儿来偷吃稻米，并且每天会增加一只鸟儿（第一天1只，第二天2只……），每只鸟儿一次吃一粒稻米。如果晚上剩下的稻米不够鸟儿吃了，那没吃到的鸟儿只能回去睡觉了。 朋友故事还没说完,lls脑海中瞬间想到稻米终将会吃完，并一会儿就指出了粮仓第一次为空的那天。现在你要完成同样的事。
第一行为两个整数n(1≤n,m≤10^18)，分别表示粮仓的容量和每天早上加入的稻米数。 从第一天早上开始计天数（即第一天晚上会有鸟儿来吃）
输出粮仓第一次为空的那天
样例一： 5 2 样例二： 8 1
样例一： 4 样例二： 5
题解
手算一下,可以发现前m天，鸟吃的都刚好能被补上
而m天后,前m只鸟消耗每天的补给,剩下的鸟消耗仓库的存粮
因此计算 (1+t)*t/2 >= n 即可
解出最小的符合要求的 t 然后加上 m 就是答案
由于数据非常大,可以使用unsigned long long
解方程部分使用二分查找
n最大为1e18,解集取为1e10确保覆盖所有解
如果n<m,那么直接输出n
代码
{% fold 点击显/隐代码 %}```cpp lls和神话故事 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
#include
#include
#include
using namespace std;
typedef unsigned long long LL;
LL n,m;
// (1+t)*t/2 >= m min(t)+m
int main(){
cin.sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
LL l=0,r=1e10;
LL t=0;
while(l<r){
t = (l+r)/2;
if(t*(t+1) >= (n-m)*2)
r = t;
else
l = t + 1;
// cout << l <<" " << r << endl;
}
cout << l + m << endl;
return 0;
}
{% endfold %}