Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <algorithm>
- #include <vector>
- #include <string>
- #include <cmath>
- #include <queue>
- using namespace std;
- const int inf = 1000000000;
- int gcd(int a, int b)
- {
- int c;
- while (a != 0) {
- c = a; a = b % a; b = c;
- }
- return b;
- }
- int obr(int r, int s) {
- for (int i = 0; i < 100000; i++)
- if (((i * r) % s) == 1)
- return i;
- return -1;
- }
- int a[1000000], b[1000000], c[1000000];
- int main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- ios_base::sync_with_stdio(false);
- int r, s, n;
- cin >> r >> s >> n;
- if (gcd(r, s) != 1)
- return !(cout << "ERROR: r, s not simple!");
- int r_star = obr(r, s);
- int r_sh = r_star * n % s;
- // инициализация
- a[0] = s;
- b[0] = 0;
- c[0] = 0;
- a[1] = r_star * r_sh % s;
- b[1] = 1;
- c[1] = (n - r * r_sh) / s * r_star % s;
- for (int i = 0; i < n; i++) {
- if (i >= 2) {
- int q = a[i - 2] / a[i - 1];
- if (i % 2 != 0)
- q = 1;
- a[i] = a[i - 2] - q * a[i - 1];
- b[i] = b[i - 2] - q * b[i - 1];
- c[i] = c[i - 2] - q * c[i - 1] % s;
- }
- vector<int> con(2, -1);
- for (int j = 1; j < s - 1; j += 2) {
- if (j == c[i] % s && abs(j) < s)
- if (con[0] == -1)
- con[0] = j;
- else
- con[1] = j;
- }
- for (int j = 2; j < s; j += 2) {
- if (j == c[i] % s
- && 2 * a[i] * b[i] <= j
- && j <= n / (s * s) + a[i] * b[i]) {
- if (con[0] == -1)
- con[0] = j;
- else
- con[1] = j;
- }
- }
- for (int j = 0; j < 2; j++) {
- if (con[j] == -1) continue;
- cout << con[j] << endl;
- int d, x1, x2, x = 0, y = 0;
- 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;
- if (d < 0)
- break;
- x1 = (con[j] * s + a[i] * r + b[i] * r_sh + sqrt((double)d)) / 2;
- x2 = (con[j] * s + a[i] * r + b[i] * r_sh - sqrt((double)d)) / 2;
- if (a[i] == 0)
- break;
- if (a[i] != 0 && b[i] != 0 && ((x1 % a[i] == 0 && x2 % b[i] == 0) || (x1 % b[i] == 0 && x2 % a[i] == 0))) {
- x = (x1 - r * a[i]) / s * a[i];
- y = (x2 - r_sh * b[i]) / s * b[i];
- }
- if (x > 0 && y > 0) {
- cout << "dopolnenie: " << x*s + r << endl;
- }
- }
- if (a[i] == 0)
- break;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement