fork download
copy 
  1. // Sky's the limit :)
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define int long long
  5.  
  6. /*
  7.     Linear Diophantine Equation
  8.     - https://c...content-available-to-author-only...s.com/algebra/linear-diophantine-equation.html
  9.     - A LDE (in two variables) is an equation of the general form: a * x + b * y = c where a, b, c are given integers, 
  10.       and x, y are unknown integers.
  11.  
  12.     Special case
  13.     - a = b = 0, if c = 0 we have infinitely many solutions, else no solutions.
  14.     
  15.     Finding any solution:
  16.     - Find solution for abs(a) * x + abs(b) * y = 1
  17.     - Multiply it by c / g, where g = gcd(a, b)
  18.     - Adjust parity
  19.  
  20.     Finding all solutions:
  21.     - Find any solution. Let it be (x0, y0)
  22.     - Then all (x, y) such that x = x0 + k * (b / g), y = y0 - k * (a / g) are solution of given LDE
  23.  
  24.     Problems
  25.     - https://c...content-available-to-author-only...s.com/gym/100963 J
  26.  
  27. */
  28.  
  29. const int INF = 1e9;
  30.  
  31. // Helper function for find_any_solution()
  32. int gcd(int a, int b, int& x, int& y) {
  33.     if (b == 0) {
  34.         x = 1;
  35.         y = 0;
  36.         return a;
  37.     }
  38.     int x1, y1;
  39.     int d = gcd(b, a % b, x1, y1);
  40.     x = y1;
  41.     y = x1 - y1 * (a / b);
  42.     return d;
  43. }
  44.  
  45. bool find_any_solution(int a, int b, int c, int &x0, int &y0, int &g) {
  46.     g = gcd(abs(a), abs(b), x0, y0);
  47.     if (c % g) {
  48.         return false;
  49.     }
  50.  
  51.     x0 *= c / g;
  52.     y0 *= c / g;
  53.     if (a < 0) x0 = -x0;
  54.     if (b < 0) y0 = -y0;
  55.     return true;
  56. }
  57.  
  58. // Helper function for find_all_solutions()
  59. void shift_solution(int &x, int &y, int a, int b, int cnt) {
  60.     x += cnt * b;
  61.     y -= cnt * a;
  62. }
  63.  
  64. // This computes the number of solutions in given range and first and last valid x for solution.
  65. // All (x, y) are solutions in given range where x = lx + k * (b / g) and y can be found from the equation.
  66. int count_solutions(int a, int b, int c, int minx, int maxx, int miny, int maxy) {
  67.     int x, y, g;
  68.     if (!find_any_solution(a, b, c, x, y, g))
  69.         return 0;
  70.     a /= g;
  71.     b /= g;
  72.  
  73.     int sign_a = a > 0 ? +1 : -1;
  74.     int sign_b = b > 0 ? +1 : -1;
  75.  
  76.     shift_solution(x, y, a, b, (minx - x) / b);
  77.     if (x < minx)
  78.         shift_solution(x, y, a, b, sign_b);
  79.     if (x > maxx)
  80.         return 0;
  81.     int lx1 = x;
  82.  
  83.     shift_solution(x, y, a, b, (maxx - x) / b);
  84.     if (x > maxx)
  85.         shift_solution(x, y, a, b, -sign_b);
  86.     int rx1 = x;
  87.  
  88.     shift_solution(x, y, a, b, -(miny - y) / a);
  89.     if (y < miny)
  90.         shift_solution(x, y, a, b, -sign_a);
  91.     if (y > maxy)
  92.         return 0;
  93.     int lx2 = x;
  94.  
  95.     shift_solution(x, y, a, b, -(maxy - y) / a);
  96.     if (y > maxy)
  97.         shift_solution(x, y, a, b, sign_a);
  98.     int rx2 = x;
  99.  
  100.     if (lx2 > rx2)
  101.         swap(lx2, rx2);
  102.     int lx = max(lx1, lx2);
  103.     int rx = min(rx1, rx2);
  104.  
  105.     if (lx > rx)
  106.         return 0;
  107.     return (rx - lx) / abs(b) + 1;
  108. }
  109.  
  110. const int MIN_X = 1;
  111. const int MAX_X = INF;
  112. const int MIN_Y = 1;
  113. const int MAX_Y = INF;
  114. vector<pair<int, int>> vec = {{1, 0}, {0, 1}};
  115.  
  116. void run_case() {
  117. 	int c;
  118. 	cin >> c;
  119.  
  120. 	int res = 0;
  121. 	// a * x + b * y = n
  122. 	for (int i = 2; i < vec.size(); i++) {
  123. 		auto &[a, b] = vec[i];
  124. 		int curr = count_solutions(a, b, c, MIN_X, MAX_X, MIN_Y, MAX_Y);
  125. 		res += curr; 
  126. 	}
  127. 	cout << res << '\n';
  128. }
  129.  
  130. signed main() {
  131.     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  132.  
  133.     for (int i = 2; i < 47; i++) {
  134.     	auto &[x1, y1] = vec[i - 1];
  135.     	auto &[x2, y2] = vec[i - 2];
  136.     	vec.push_back({x1 + x2, y1 + y2});
  137.     }
  138.  
  139.     int T = 1; 
  140.     cin >> T; 
  141.     while (T--) {
  142.     	run_case();
  143.     }
  144.  
  145.     return 0;
  146. }
  147.  
Success #stdin #stdout 0s 4724KB
comments (?)
stdin
copy 
1
14
stdout
copy 
22
https://ideone.com/PT80Ce
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!