Advertisement
Guest User

Untitled

a guest
Apr 23rd, 2017
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.31 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <string>
  6. #include <cmath>
  7. #include <queue>
  8.  
  9. using namespace std;
  10.  
  11.  
  12. const int inf = 1000000000;
  13.  
  14. int gcd(int a, int b)
  15. {
  16. int c;
  17. while (a != 0) {
  18. c = a; a = b % a; b = c;
  19. }
  20. return b;
  21. }
  22.  
  23. int obr(int r, int s) {
  24. for (int i = 0; i < 100000; i++)
  25. if (((i * r) % s) == 1)
  26. return i;
  27. return -1;
  28. }
  29.  
  30. int a[1000000], b[1000000], c[1000000];
  31.  
  32. int main() {
  33. #ifdef _DEBUG
  34. freopen("input.txt", "r", stdin);
  35. freopen("output.txt", "w", stdout);
  36. #endif
  37. ios_base::sync_with_stdio(false);
  38.  
  39. int r, s, n;
  40.  
  41. cin >> r >> s >> n;
  42.  
  43. if (gcd(r, s) != 1)
  44. return !(cout << "ERROR: r, s not simple!");
  45.  
  46. int r_star = obr(r, s);
  47. int r_sh = r_star * n % s;
  48.  
  49. // инициализация
  50. a[0] = s;
  51. b[0] = 0;
  52. c[0] = 0;
  53.  
  54. a[1] = r_star * r_sh % s;
  55. b[1] = 1;
  56. c[1] = (n - r * r_sh) / s * r_star % s;
  57.  
  58.  
  59.  
  60. for (int i = 0; i < n; i++) {
  61.  
  62. if (i >= 2) {
  63. int q = a[i - 2] / a[i - 1];
  64. if (i % 2 != 0)
  65. q = 1;
  66. a[i] = a[i - 2] - q * a[i - 1];
  67. b[i] = b[i - 2] - q * b[i - 1];
  68. c[i] = c[i - 2] - q * c[i - 1] % s;
  69. }
  70.  
  71.  
  72. vector<int> con(2, -1);
  73.  
  74. for (int j = 1; j < s - 1; j += 2) {
  75. if (j == c[i] % s && abs(j) < s)
  76. if (con[0] == -1)
  77. con[0] = j;
  78. else
  79. con[1] = j;
  80. }
  81. for (int j = 2; j < s; j += 2) {
  82. if (j == c[i] % s
  83. && 2 * a[i] * b[i] <= j
  84. && j <= n / (s * s) + a[i] * b[i]) {
  85. if (con[0] == -1)
  86. con[0] = j;
  87. else
  88. con[1] = j;
  89. }
  90. }
  91.  
  92.  
  93. for (int j = 0; j < 2; j++) {
  94. if (con[j] == -1) continue;
  95. cout << con[j] << endl;
  96.  
  97. int d, x1, x2, x = 0, y = 0;
  98. d = (con[j] * s + a[i] * r + b[i] * r_sh) * (con[j] * s + a[i] * r + b[i] * r_sh) - 4 * a[i] * b[i] * n;
  99. if (d < 0)
  100. break;
  101. x1 = (con[j] * s + a[i] * r + b[i] * r_sh + sqrt((double)d)) / 2;
  102. x2 = (con[j] * s + a[i] * r + b[i] * r_sh - sqrt((double)d)) / 2;
  103.  
  104. if (a[i] == 0)
  105. break;
  106.  
  107. if (a[i] != 0 && b[i] != 0 && ((x1 % a[i] == 0 && x2 % b[i] == 0) || (x1 % b[i] == 0 && x2 % a[i] == 0))) {
  108. x = (x1 - r * a[i]) / s * a[i];
  109. y = (x2 - r_sh * b[i]) / s * b[i];
  110. }
  111. if (x > 0 && y > 0) {
  112. cout << "dopolnenie: " << x*s + r << endl;
  113. }
  114.  
  115. }
  116.  
  117. if (a[i] == 0)
  118. break;
  119. }
  120. return 0;
  121. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement