CF1744E1 Divisible Numbers (easy version)

题意

给你四个数 \(a,b,c,d\)，你需要找出一组 \(x,y\) 使得 \(a<x\leq c,b<y\leq d\) 并且 \(x\cdot y\) 能被 \(a\cdot b\) 整除，如果没有输出 -1 -1。

思路

最暴力的思路肯定是枚举，更肯定的一点是会TLE

但是注意到，如果\(x\)一定，那么他的\(xy\)越大，\(y\)也就越大

换句话说，当\(x\)一定时，\(xy\)和\(y\)呈正比，也就是有单调性

那么考虑二分，即每次枚举\(x\)，看看当前情况下能否构造出一个符合条件的\(y\)即可

再来看看细节：

• 如何二分：

  注意到存在一个\(k\)使得\(\frac{ab}{gcd(ab,x)}\times k=y\)，并且\(x\)和\(y\)均符合条件，所以二分\(k\)即可

• 如何check：

  这道题的check需要分成三种状态：

  1. 符合题目要求

  2. \(y\leq b\)

  3. \(y>d\)

  只需要让他在不同状态下返回值不同即可。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,c,d,Lcm;
int check(ll i)
{
    ll y=Lcm*i;
    if(b<y && y<=d) return 1;
    else if(y<=b) return 2;
    else return 0;
}
int find(ll x)
{
    ll l,r,mid,ans=0;l=1,r=1e5;
    while(l<=r)
    {
        mid=(l+r)>>1;
        int re=check(mid);
        if(re==1)
        {
            ans=mid*Lcm;
            break;
        }
        else if(re==2) l=mid+1;
        else r=mid-1;
    }
    return ans;
}
void run()
{
    cin>>a>>b>>c>>d;
    for(int i=a+1;i<=c;i++)
    {
        Lcm=a*b/__gcd(a*b,(ll)i);
        if(find(i))
        {
            cout<<i<<" "<<find(i)<<endl;
            return;
        }
    }
    cout<<-1<<" "<<-1<<endl;
}
int main()
{
    int t;
    cin>>t;
    while(t--) run();
}