Advertisement
Lazit

Untitled

Jan 18th, 2020
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.87 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <chrono>
  3. #include <random>
  4. #include <cassert>
  5. #include <type_traits>
  6. #include <unordered_map>
  7. //#pragma comment(linker, "/STACK:16777216")
  8.  
  9. using namespace std;
  10.  
  11. typedef long double C;
  12. typedef complex<C> P;
  13.  
  14. #define X real()
  15. #define Y imag()
  16. #define have(X, Y) (X.find(Y) != X.end())
  17. #define int long long
  18. #define Size(X) (int)X.size()
  19. #define ui unsigned int
  20. #define endl '\n'
  21. #define mp make_pair
  22. #define timer fghge
  23. #define y1 yjyjyju
  24. #define all(X) (X).begin(), (X).end()
  25.  
  26. mt19937_64 rnd(std::chrono::steady_clock::now().time_since_epoch().count());
  27.  
  28. int gcd(int a, int b) {
  29. if (b == 0)
  30. return a;
  31. else
  32. return gcd(b, a % b);
  33. }
  34.  
  35. void extgcd(int a, int b, int &x, int &y) {
  36. if (b == 0) {
  37. x = 1;
  38. y = 0;
  39. }
  40. else {
  41. int xt, yt;
  42. extgcd(b, a % b, xt, yt);
  43. x = yt;
  44. int n = a / b;
  45. y = xt - n * yt;
  46. }
  47. }
  48.  
  49.  
  50.  
  51. int ceil(double a, double b) {
  52. double ans = ceil(a / b);
  53. if ((int)a % (int)b == 0)
  54. ans++;
  55. return ans;
  56. }
  57.  
  58. int floor(double a, double b) {
  59. double ans = floor(a / b);
  60. if ((int)a % (int)b == 0)
  61. ans--;
  62. return ans;
  63. }
  64.  
  65. signed main() {
  66. ios_base::sync_with_stdio(0);
  67. cin.tie(0), cout.tie(0);
  68. freopen("input.txt", "r", stdin);
  69.  
  70. int n, x; cin >> n >> x;
  71. int ans = 0;
  72. for (int i = 2; i <= 3000; i++) {
  73. for (int j = 1; j < i; j++) {
  74. int a = i, b = -j, c = n;
  75. int g = gcd(a, b);
  76. if (c % g == 0) {
  77. int x, y;
  78. extgcd(a, b, x, y);
  79. x *= c / g; y *= c / g;
  80.  
  81. int fir = b / g, sec = -a / g;
  82. int k;
  83. if (fir - sec > 0)
  84. k = ceil(y - x, fir - sec);
  85. else
  86. k = floor(y - x, fir - sec);
  87.  
  88. x += k * fir;
  89. y += k * sec;
  90.  
  91. if (x <= y) {
  92. cout << "fail";
  93. }
  94. if (y > 0) {
  95. ans++;
  96. int d = y / sec;
  97. if (y % sec == 0)
  98. d--;
  99. ans += d;
  100. }
  101. }
  102. }
  103. }
  104. cout << ans;
  105. return 0;
  106. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement