Problem about GCD

题面翻译

题目描述

给出三个整数 $l,r,G$，要求找到一个数对 $A,B$ 满足 $l\le A\le B\le r$ 且 $\gcd (A,B) = G$，并且满足 $\left\vert A-B \right\vert$ 最大。

如果有多组解，选择 $A$ 的值最小的一个。

输入格式

第一行一个整数 $T$，表示测试点数量。

之后 $T$ 行每行三个整数 $l,r,G$，含义同题目描述。

输出格式

$T$ 行，每行两个数 $A,B$ 表示该测试点的答案。

数据范围

$1\le t\le 10^3$

$1\le l\le r\le 10^{18}$

$1\le G\le 10^{18}$

题目描述

Given three integers $ l $ , $ r $ , and $ G $ , find two integers $ A $ and $ B $ ( $ l \le A \le B \le 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 \le t \le 10^3 $ ) — 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 \le l \le r \le 10^{18} $ ; $ 1 \le G \le 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.

样例 #1

样例输入 #1

4
4 8 2
4 8 3
4 8 4
5 7 6

样例输出 #1

4 6
-1 -1
4 8
6 6

在区间内可以满足题目要求的，即是A和B都是g的倍数，但是，他们的gcd只可以是g，不能是g的倍数，要做到这一条件，A=xg，B=yg，其中，x和y必须是互质，也就是gcd(x,y)==1才可以，才能满足gcd(A,B)为g，题目要求A和B距离最远，又要A最小，所以必须先枚举A和B的距离，从大到小，再枚举A开始的地方

const int N = 2e5 + 10;
long long gcd(long long aa, long long bb) { return bb ? gcd(bb, aa % bb) : aa; }

void solve()
{
    int l, r, g; cin >> l >> r >> g;
    int a, b;
    if (l % g == 0) a = l;
    else a = (g - (l % g)) + l;
    if (a > r)
    {
        cout << "-1 -1" << '\n';
        return;
    }
    b = (r / g) * g;
    int x = a / g;
    int y = b / g;
    int len = y - x;
    for (int i = len; i >= 0; i--)
    {
        for (int j = x; j <= y; j++)
        {
            if (j + i <= y)
            {
                if (gcd(j, j + i) == 1)
                {
                    cout << j * g << " " << (j + i) * g << '\n';
                    return;
                }
            }
            else break;
        }
    }
    cout << -1 << " " << -1 << '\n';
}