12712 - Got flunked
raw download clone
CPP
views 7
,
size 1121 b
#include <iostream>
#include <cmath>

using namespace std;

long long f(long long num, long long p) {
    return num * p + (num - 1) * num / 2;
}

long long BS(long long n, long long p, long long sq) {
    long long low = 1;
    long long high = (p > 0) ? min(sq, n/p): sq;

    while (low <= high) {
        long long mid = (low + high) >> 1;
        long long ff = f(mid, p);

        if (ff < n) {
            low = mid + 1;
        } else if(ff > n) {
            high = mid - 1;
        } else {
            return mid;
        }
    }

    return -1;
}

int main() {
    int T;
    long long n;
    double log2 = log(2);

    cin >> T;
    while (T-- > 0) {
        cin >> n;
        int limit = (int)(log(n) / log2);
        long long num = -1;
        long long sq = (long)sqrt(2 * n) + 1;
        for (int i=limit+1; i>=0; i--) {
            long long tmp = BS(n, ((long)1 << i) - 1, sq);
            if (tmp != -1 && (tmp & 1) == 1) {
                num = tmp * ((long long)1 << i);
            }
        }
        cout << num << "\n";
    }

    return 0;
}
close fullscreen
Login or Register to edit or fork this paste. It's free.