http://codeforces.com/gym/100283/problem/F
思路是二分第几行，二分出来的行是总和 >= n的，那么第k - 1行一定要选，那么再在第k行中二分那一列、
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> #include <bitset> LL f1(LL n) { return n * (n + 1) / 2 * (2 * n + 1) / 3; } LL f2(int which, int pos) { if (pos <= which) { return 1LL * pos * (1 + pos) / 2; } else { LL t = 2 * which - 1 - pos; return 1LL * which * (1 + which) - which - f2(which, t); } } void work() { LL n; scanf("%I64d", &n); int be = 1, en = 2e6 + 20; while (be <= en) { int mid = (be + en) >> 1; LL res = f1(mid); if (res >= n) { en = mid - 1; } else be = mid + 1; } // cout << be << endl; // cout << f1(be) << endl; LL ans = ((LL)be - 1) * (be - 1); // cout << n << endl; // cout << f1(be - 1) << endl; n -= f1(be - 1); // cout << n << endl; // cout << f2(4, 8) << endl; int L = 1, R = 2 * be - 1; while (L <= R) { int mid = (L + R) >> 1; LL res = f2(be, mid); if (res >= n) { R = mid - 1; } else L = mid + 1; } ans += L; static int f = 0; printf("Case %d: %I64d ", ++f, ans); } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif // freopen("army.in", "r", stdin); int t; scanf("%d", &t); while (t--) work(); return 0; }