// Sky's the limit :)
#include <bits/stdc++.h>
using namespace std;
#define int long long
/*
Linear Diophantine Equation
- https://c...content-available-to-author-only...s.com/algebra/linear-diophantine-equation.html
- A LDE (in two variables) is an equation of the general form: a * x + b * y = c where a, b, c are given integers,
and x, y are unknown integers.
Special case
- a = b = 0, if c = 0 we have infinitely many solutions, else no solutions.
Finding any solution:
- Find solution for abs(a) * x + abs(b) * y = 1
- Multiply it by c / g, where g = gcd(a, b)
- Adjust parity
Finding all solutions:
- Find any solution. Let it be (x0, y0)
- Then all (x, y) such that x = x0 + k * (b / g), y = y0 - k * (a / g) are solution of given LDE
Problems
- https://c...content-available-to-author-only...s.com/gym/100963 J
*/
const int INF = 1e9;
// Helper function for find_any_solution()
int gcd(int a, int b, int& x, int& y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
int x1, y1;
int d = gcd(b, a % b, x1, y1);
x = y1;
y = x1 - y1 * (a / b);
return d;
}
bool find_any_solution(int a, int b, int c, int &x0, int &y0, int &g) {
g = gcd(abs(a), abs(b), x0, y0);
if (c % g) {
return false;
}
x0 *= c / g;
y0 *= c / g;
if (a < 0) x0 = -x0;
if (b < 0) y0 = -y0;
return true;
}
// Helper function for find_all_solutions()
void shift_solution(int &x, int &y, int a, int b, int cnt) {
x += cnt * b;
y -= cnt * a;
}
// This computes the number of solutions in given range and first and last valid x for solution.
// All (x, y) are solutions in given range where x = lx + k * (b / g) and y can be found from the equation.
int count_solutions(int a, int b, int c, int minx, int maxx, int miny, int maxy) {
int x, y, g;
if (!find_any_solution(a, b, c, x, y, g))
return 0;
a /= g;
b /= g;
int sign_a = a > 0 ? +1 : -1;
int sign_b = b > 0 ? +1 : -1;
shift_solution(x, y, a, b, (minx - x) / b);
if (x < minx)
shift_solution(x, y, a, b, sign_b);
if (x > maxx)
return 0;
int lx1 = x;
shift_solution(x, y, a, b, (maxx - x) / b);
if (x > maxx)
shift_solution(x, y, a, b, -sign_b);
int rx1 = x;
shift_solution(x, y, a, b, -(miny - y) / a);
if (y < miny)
shift_solution(x, y, a, b, -sign_a);
if (y > maxy)
return 0;
int lx2 = x;
shift_solution(x, y, a, b, -(maxy - y) / a);
if (y > maxy)
shift_solution(x, y, a, b, sign_a);
int rx2 = x;
if (lx2 > rx2)
swap(lx2, rx2);
int lx = max(lx1, lx2);
int rx = min(rx1, rx2);
if (lx > rx)
return 0;
return (rx - lx) / abs(b) + 1;
}
const int MIN_X = 1;
const int MAX_X = INF;
const int MIN_Y = 1;
const int MAX_Y = INF;
vector<pair<int, int>> vec = {{1, 0}, {0, 1}};
void run_case() {
int c;
cin >> c;
int res = 0;
// a * x + b * y = n
for (int i = 2; i < vec.size(); i++) {
auto &[a, b] = vec[i];
int curr = count_solutions(a, b, c, MIN_X, MAX_X, MIN_Y, MAX_Y);
res += curr;
}
cout << res << '\n';
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
for (int i = 2; i < 47; i++) {
auto &[x1, y1] = vec[i - 1];
auto &[x2, y2] = vec[i - 2];
vec.push_back({x1 + x2, y1 + y2});
}
int T = 1;
cin >> T;
while (T--) {
run_case();
}
return 0;
}
Ly8gU2t5J3MgdGhlIGxpbWl0IDopCiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwojZGVmaW5lIGludCBsb25nIGxvbmcKCi8qCiAgICBMaW5lYXIgRGlvcGhhbnRpbmUgRXF1YXRpb24KICAgIC0gaHR0cHM6Ly9jLi4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5zLmNvbS9hbGdlYnJhL2xpbmVhci1kaW9waGFudGluZS1lcXVhdGlvbi5odG1sCiAgICAtIEEgTERFIChpbiB0d28gdmFyaWFibGVzKSBpcyBhbiBlcXVhdGlvbiBvZiB0aGUgZ2VuZXJhbCBmb3JtOiBhICogeCArIGIgKiB5ID0gYyB3aGVyZSBhLCBiLCBjIGFyZSBnaXZlbiBpbnRlZ2VycywgCiAgICAgIGFuZCB4LCB5IGFyZSB1bmtub3duIGludGVnZXJzLgoKICAgIFNwZWNpYWwgY2FzZQogICAgLSBhID0gYiA9IDAsIGlmIGMgPSAwIHdlIGhhdmUgaW5maW5pdGVseSBtYW55IHNvbHV0aW9ucywgZWxzZSBubyBzb2x1dGlvbnMuCiAgICAKICAgIEZpbmRpbmcgYW55IHNvbHV0aW9uOgogICAgLSBGaW5kIHNvbHV0aW9uIGZvciBhYnMoYSkgKiB4ICsgYWJzKGIpICogeSA9IDEKICAgIC0gTXVsdGlwbHkgaXQgYnkgYyAvIGcsIHdoZXJlIGcgPSBnY2QoYSwgYikKICAgIC0gQWRqdXN0IHBhcml0eQoKICAgIEZpbmRpbmcgYWxsIHNvbHV0aW9uczoKICAgIC0gRmluZCBhbnkgc29sdXRpb24uIExldCBpdCBiZSAoeDAsIHkwKQogICAgLSBUaGVuIGFsbCAoeCwgeSkgc3VjaCB0aGF0IHggPSB4MCArIGsgKiAoYiAvIGcpLCB5ID0geTAgLSBrICogKGEgLyBnKSBhcmUgc29sdXRpb24gb2YgZ2l2ZW4gTERFCgogICAgUHJvYmxlbXMKICAgIC0gaHR0cHM6Ly9jLi4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5zLmNvbS9neW0vMTAwOTYzIEoKCiovCgpjb25zdCBpbnQgSU5GID0gMWU5OwoKLy8gSGVscGVyIGZ1bmN0aW9uIGZvciBmaW5kX2FueV9zb2x1dGlvbigpCmludCBnY2QoaW50IGEsIGludCBiLCBpbnQmIHgsIGludCYgeSkgewogICAgaWYgKGIgPT0gMCkgewogICAgICAgIHggPSAxOwogICAgICAgIHkgPSAwOwogICAgICAgIHJldHVybiBhOwogICAgfQogICAgaW50IHgxLCB5MTsKICAgIGludCBkID0gZ2NkKGIsIGEgJSBiLCB4MSwgeTEpOwogICAgeCA9IHkxOwogICAgeSA9IHgxIC0geTEgKiAoYSAvIGIpOwogICAgcmV0dXJuIGQ7Cn0KCmJvb2wgZmluZF9hbnlfc29sdXRpb24oaW50IGEsIGludCBiLCBpbnQgYywgaW50ICZ4MCwgaW50ICZ5MCwgaW50ICZnKSB7CiAgICBnID0gZ2NkKGFicyhhKSwgYWJzKGIpLCB4MCwgeTApOwogICAgaWYgKGMgJSBnKSB7CiAgICAgICAgcmV0dXJuIGZhbHNlOwogICAgfQoKICAgIHgwICo9IGMgLyBnOwogICAgeTAgKj0gYyAvIGc7CiAgICBpZiAoYSA8IDApIHgwID0gLXgwOwogICAgaWYgKGIgPCAwKSB5MCA9IC15MDsKICAgIHJldHVybiB0cnVlOwp9CgovLyBIZWxwZXIgZnVuY3Rpb24gZm9yIGZpbmRfYWxsX3NvbHV0aW9ucygpCnZvaWQgc2hpZnRfc29sdXRpb24oaW50ICZ4LCBpbnQgJnksIGludCBhLCBpbnQgYiwgaW50IGNudCkgewogICAgeCArPSBjbnQgKiBiOwogICAgeSAtPSBjbnQgKiBhOwp9CgovLyBUaGlzIGNvbXB1dGVzIHRoZSBudW1iZXIgb2Ygc29sdXRpb25zIGluIGdpdmVuIHJhbmdlIGFuZCBmaXJzdCBhbmQgbGFzdCB2YWxpZCB4IGZvciBzb2x1dGlvbi4KLy8gQWxsICh4LCB5KSBhcmUgc29sdXRpb25zIGluIGdpdmVuIHJhbmdlIHdoZXJlIHggPSBseCArIGsgKiAoYiAvIGcpIGFuZCB5IGNhbiBiZSBmb3VuZCBmcm9tIHRoZSBlcXVhdGlvbi4KaW50IGNvdW50X3NvbHV0aW9ucyhpbnQgYSwgaW50IGIsIGludCBjLCBpbnQgbWlueCwgaW50IG1heHgsIGludCBtaW55LCBpbnQgbWF4eSkgewogICAgaW50IHgsIHksIGc7CiAgICBpZiAoIWZpbmRfYW55X3NvbHV0aW9uKGEsIGIsIGMsIHgsIHksIGcpKQogICAgICAgIHJldHVybiAwOwogICAgYSAvPSBnOwogICAgYiAvPSBnOwoKICAgIGludCBzaWduX2EgPSBhID4gMCA/ICsxIDogLTE7CiAgICBpbnQgc2lnbl9iID0gYiA+IDAgPyArMSA6IC0xOwoKICAgIHNoaWZ0X3NvbHV0aW9uKHgsIHksIGEsIGIsIChtaW54IC0geCkgLyBiKTsKICAgIGlmICh4IDwgbWlueCkKICAgICAgICBzaGlmdF9zb2x1dGlvbih4LCB5LCBhLCBiLCBzaWduX2IpOwogICAgaWYgKHggPiBtYXh4KQogICAgICAgIHJldHVybiAwOwogICAgaW50IGx4MSA9IHg7CgogICAgc2hpZnRfc29sdXRpb24oeCwgeSwgYSwgYiwgKG1heHggLSB4KSAvIGIpOwogICAgaWYgKHggPiBtYXh4KQogICAgICAgIHNoaWZ0X3NvbHV0aW9uKHgsIHksIGEsIGIsIC1zaWduX2IpOwogICAgaW50IHJ4MSA9IHg7CgogICAgc2hpZnRfc29sdXRpb24oeCwgeSwgYSwgYiwgLShtaW55IC0geSkgLyBhKTsKICAgIGlmICh5IDwgbWlueSkKICAgICAgICBzaGlmdF9zb2x1dGlvbih4LCB5LCBhLCBiLCAtc2lnbl9hKTsKICAgIGlmICh5ID4gbWF4eSkKICAgICAgICByZXR1cm4gMDsKICAgIGludCBseDIgPSB4OwoKICAgIHNoaWZ0X3NvbHV0aW9uKHgsIHksIGEsIGIsIC0obWF4eSAtIHkpIC8gYSk7CiAgICBpZiAoeSA+IG1heHkpCiAgICAgICAgc2hpZnRfc29sdXRpb24oeCwgeSwgYSwgYiwgc2lnbl9hKTsKICAgIGludCByeDIgPSB4OwoKICAgIGlmIChseDIgPiByeDIpCiAgICAgICAgc3dhcChseDIsIHJ4Mik7CiAgICBpbnQgbHggPSBtYXgobHgxLCBseDIpOwogICAgaW50IHJ4ID0gbWluKHJ4MSwgcngyKTsKCiAgICBpZiAobHggPiByeCkKICAgICAgICByZXR1cm4gMDsKICAgIHJldHVybiAocnggLSBseCkgLyBhYnMoYikgKyAxOwp9Cgpjb25zdCBpbnQgTUlOX1ggPSAxOwpjb25zdCBpbnQgTUFYX1ggPSBJTkY7CmNvbnN0IGludCBNSU5fWSA9IDE7CmNvbnN0IGludCBNQVhfWSA9IElORjsKdmVjdG9yPHBhaXI8aW50LCBpbnQ+PiB2ZWMgPSB7ezEsIDB9LCB7MCwgMX19OwoKdm9pZCBydW5fY2FzZSgpIHsKCWludCBjOwoJY2luID4+IGM7CgoJaW50IHJlcyA9IDA7CgkvLyBhICogeCArIGIgKiB5ID0gbgoJZm9yIChpbnQgaSA9IDI7IGkgPCB2ZWMuc2l6ZSgpOyBpKyspIHsKCQlhdXRvICZbYSwgYl0gPSB2ZWNbaV07CgkJaW50IGN1cnIgPSBjb3VudF9zb2x1dGlvbnMoYSwgYiwgYywgTUlOX1gsIE1BWF9YLCBNSU5fWSwgTUFYX1kpOwoJCXJlcyArPSBjdXJyOyAKCX0KCWNvdXQgPDwgcmVzIDw8ICdcbic7Cn0KCnNpZ25lZCBtYWluKCkgewogICAgaW9zOjpzeW5jX3dpdGhfc3RkaW8oMCk7IGNpbi50aWUoMCk7IGNvdXQudGllKDApOwogICAgCQogICAgZm9yIChpbnQgaSA9IDI7IGkgPCA0NzsgaSsrKSB7CiAgICAJYXV0byAmW3gxLCB5MV0gPSB2ZWNbaSAtIDFdOwogICAgCWF1dG8gJlt4MiwgeTJdID0gdmVjW2kgLSAyXTsKICAgIAl2ZWMucHVzaF9iYWNrKHt4MSArIHgyLCB5MSArIHkyfSk7CiAgICB9CgogICAgaW50IFQgPSAxOyAKICAgIGNpbiA+PiBUOyAKICAgIHdoaWxlIChULS0pIHsKICAgIAlydW5fY2FzZSgpOwogICAgfQogICAgCiAgICByZXR1cm4gMDsKfQo=