1 月 18 日

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$ ，所以最多几十次就会找到一个质数，而质数和任何数字都是互质的。所以我们找两个互质的数只会更快。

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

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";
}

明天再写（）。