2025-01-18

今天又是什么都没写的一天，就晚上看了一个题目。

自从1月11号回家到今天，一个星期多了，一直在玩，写题很少，要稍微多写一点了。太废了。。。

刚才看了CF2043D，花了一小时多时间才AC，而且还看了题解才写出来。

是一个 *1800 的题目，但是感觉没有很难的。。。但是我不会写。

题目大意

给三个数字，\(l\) ,\(r\), \(G\), 找出两个数字 \(A\) 和 \(B\) ，使得它们的最大公约数(GCD)等于 \(G\) 并且 \(|A-B|\) 最大。

如果有多对这样的数字，选择 \(A\) 最小的。如果不存在，输出 "-1 -1"。

输入三个数字 \(l\), \(r\) , \(G\) (\(1\le l\le r\le10^{18}\); $1\le G\le10^{18} $)

思路

由于\(gcd(A,B)=G\),

所以 \(A\) 和 \(B\) 一定都是 G的倍数。

记为 \(A=aG,B=bG\) ,

所以我们需要 \(gcd(a,b)=1\),

即我们要找到 \(a, b \in [\ \lceil\frac{l}{G}\rceil\ ,\ \lfloor\frac{r}{G}\rfloor\ ]\) ，满足 \(gcd(a,b)=1\) ，且 \(|b-a|\) 最大，\(a\) 尽量小。

看起来很麻烦，但是其实两个互质的数是非常多的，所以直接暴力找并不会找很多次。

有这么一个事实，素数是密集的，说人话就是素数两两之间挨的非常近，\(\le n\) 的素数两两距离大约是 \(\log n\) ，所以最多几十次就会找到一个质数，而质数和任何数字都是互质的。所以我们找两个互质的数只会更快。

所以只需要检查每一个长度，是否可以找到合法的就彳亍了。

C++

void solve()
{
    ll l,r,G;
    cin>>l>>r>>G;
    ll tl=((l-1)/G+1)*G,tr=r/G*G;
    if(tl>r||tr<l){
        cout<<"-1 -1\n";
        return;
    }
    l=tl,r=tr;
    for(ll d=(r-l)/G;d>=1;d--){
        for(ll L=l/G;L+d<=r/G;L++){
            if(gcd(L,L+d)==1){
                cout<<L*G<<" "<<(L+d)*G<<'\n';
                return;
            }
        }
    }
    if(l==G)
        cout<<G<<" "<<G<<'\n';
    else
        cout<<"-1 -1\n";
}

明天再写（）。