题解：CF2043D Problem about GCD

题目链接

• CF2043D 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$ 的值最小的一个。

解题思路

首先 $A,B$ 肯定都是 $G$ 的倍数，所以直接将 $l,r$ 转化为 $\left\lceil \dfrac{l}{G} \right\rceil,\left\lfloor \dfrac{r}{G} \right\rfloor$，在该区间内求最远互质点对，设为 $(x ,y)$，则 $(A,B)=(x\times G,y\times G)$。

关于如何求区间内最远互质点对，可以参考 Atcoder arc137_a（站内链接）。

如果直接暴力枚举 $\left\vert x-y \right\vert$ 和 $x$，理论复杂度达到了惊人的 $O((r-l)\log a)$，看上去是不能通过的。

但是其实并不会遍历那么多次，参考上面给出的题解可知在题目给出的 $1\times 10^{18}$ 数据范围内复杂度并没有很高。

所以尽管并未算出实际复杂度期望，但是我们暴力枚举仍然可以通过本题。

参考代码

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

long long T , l , r , g;

long long gcd(long long aa , long long bb) {return bb ? gcd(bb , aa % bb) : aa;}

void solve()
{
    long long len = r - l;
    while(len >= 0)
    {
        for(long long i = l ; i <= r - len ; i++) if(gcd(i , i + len) == 1) {cout << i * g << " " << (i + len) * g << '\n'; return;}
        len--;
    }
    cout << -1 << " " << -1 << '\n';
}

int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> T;
    while(T--)
    {
        cin >> l >> r >> g;
        l += g - 1; l /= g; r /= g;
        solve();
    }
    return 0;
}

补充

以下是不严谨的关于该代码时间复杂度的证明。

参考资料

• 维基百科 克拉梅尔猜想

证明

在维基百科的这一条目中提到，托马斯·雷·奈斯利使用了公式 $R=\dfrac{\log p_n}{\sqrt{p_{n+1}-p_n}}$ 来计算素数间隙与克拉梅尔猜想相契合的程度，对于现在已知最大的素数间隙， $R$ 的值依然保持在 $1.13$ 左右。

因此该题目中最大的素数间隙（设其为 $g(i)$，且 $p_i$ 表示最大的质数间隙对应的质数对中较小的那一个）在 $(\dfrac{\log p_i}{1.13})^2$ 左右，因此即使我们并不确定 $i$ 的具体值，$g(i)$ 的值一定不会超过 $(\dfrac{\log 1e18}{1.13})^2$，而该式的值约为 $60$。

在该题目中，能够构造出的最坏情况为 $l,r$ 分别距离 $x,y$ 为 $g(i)$，此时上述代码的时间复杂度为 $g(i)^2$。

又因为我们已经证明了 $g(i)$ 的值并不会超过 $60$，所以上述代码的最坏时间复杂度为 $O(Tg(i)^2)$，不超过 $3.6\times 10^6$，显然可以通过本题。