暴力模拟
时间复杂度:$O(L2 logL)$
模拟:$A′$和$B′$
判断是否符合题意即可
代码如下:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,l,ans1,ans2;
double x,y;
double qwq=1e9;
int main()
{
cin>>a>>b>>l;
for(int i=1;i<=l;i++)
{
for(int j=1;j<=l;j++)
{
if(__gcd((int)i,(int)j)!=0)continue;
x=i*1.0/j;
y=a*1.0/b;
if(x>=y&&x-y<qwq)
{
qwq=x-y;
ans1=i;
ans2=j;
}
}
}
cout<<ans1<<" "<<ans2;
}