[Educatinal Codeforces Round 173(Div.2)] - D. Problem about GCD

https://codeforces.com/contest/2043/problem/D

Educational Codeforces Round 173(Div.2) - D. Problem about GCD

문제 유형: 수학, 브루트 포스, 그리디

시간 제한: 1초

메모리 제한: 256MB

 

문제

Given three integers l, r, and G, find two integers A and B (l≤A≤B≤r) such that their greatest common divisor (GCD) equals G and the distance |A−B| is maximized.

If there are multiple such pairs, choose the one where A is minimized. If no such pairs exist, output "-1 -1".

 

입력

The first line contains a single integer t (1≤t≤103) — the number of test cases. Then, t test cases follow.

Each test case consists of a single line containing three integers l,r,G (1≤l≤r≤10^18; 1≤G≤10^18) — the range boundaries and the required GCD.

 

출력

For each test case, output two integers A and B — the solution to the problem, or "-1 -1" if no such pair exists.

 

풀이

Editorial: https://codeforces.com/blog/entry/137801

|A-B|가 크려면, 최대한 A는 작아야 하고, B는 최대한 커야 한다.

 

새로운 범위를 만들어 주는 것이 편하다.

어차피 유효한 A, B는 G의 배수여야 한다.

그래서, 새로운 왼쪽범위 L은 l 이상의 g의배수여야 한다.

또한, 새로운 오른쪽범위 R은 r이하의 g의배수여야 한다.

i = 0부터 (R-L)/g이전까지 다음을 반복한다. 즉, i는 최소 범위와 최대 범위에서 g단위로 얼마나 더하거나 뺄 것인지에 대한 것을 다룬다.

 범위 안의 A후보(L + j*g)와 B후보(R - (i - j) * g)의 gcd를 구해서 gcd가 g이면, 정답이다. (j는 0 ~ i의 범위여야 한다.)

2중 루프를 다 돌고도 끝이나지 않는다면, "-1 -1"을 출력하면 된다.

 

코드

C++

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll gcd(int a, int b) {
  if (b == 0)
    return a;
  return gcd(b, a % b);
}

void solve() {
  ll l, r, g;
  cin >> l >> r >> g;

  ll L = l + (l % g == 0 ? 0 : g - (l % g));
  ll R = r - r % g;
  for (int i = 0; i <= (R - L) / g; ++i) {
    for (int j = 0; j <= i; j++) {
      if (gcd(L + j * g, R - (i - j) * g) == g) {
        cout << L + j * g << " " << R - (i - j) * g << "\n";
        return;
      }
    }
  }

  cout << "-1 -1\n";
}

int main(int argc, char *argv[]) {
  int t;
  cin >> t;
  while (t--)
    solve();
  return 0;
}