题解：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，显然可以通过本题。