最後1%有多筆詢問,間接禁止naive的迴圈作法
採用二分搜尋找「Kevin要拔幾次花瓣才能拔完」,因為Kevin拔了k次花瓣所拔的花瓣數可以很快求得
每筆詢問只需要O(logn),3ms內跑完,完全不須擔心TLE
#include <bits/stdc++.h>
using namespace std;
long long n,m;
long long sum(long long k) {
// 1 + (1+m) + (1+m*2) + ... + (1+m*(k-1))
return k + m*(k*(k-1)/2);
}
signed main() {
ios_base::sync_with_stdio(0),cin.tie(0);
while(cin >> n >> m) {
long long s = 1, x = 0;
while(sum(s) < n) s *= 2;
while(s) {
if(n >= sum(x+s)) x += s;
s /= 2;
}
n -= sum(x);
if(n == 0)
cout << "Go Kevin!!\n";
else
cout << "No Stop!!\n";
}
}
當然也可以用判別式O(1)判斷