算法
(枚举,欧几里得算法,数论) $O(L^2)$
由于 $L$ 在100以内,因此可以枚举 $A’, B’$ 的所有组合,然后判断:
- $A’, B’$ 是否互质;
- $\frac{A’}{B’}$ 是否大于等于 $\frac{A}{B}$,并且最小
感谢@[zhangmingjie]同学的提示,上述算法可以省去对于 $A’, B’$ 是否互质的判断:
- 我们分别从小到大枚举 $A’, B’$,那么当 $(A’, B’) = d > 1$ 时,我们一定在此之前先枚举了 $\frac{A’}{d}$ 和 $\frac{B’}{d}$,这两组的比值是相同的,所以我们一定不会选择前一组,即一定不会选择不互质的一组。
时间复杂度
$A’, B’$ 总共有 $L^2$ 种组合,因此总时间复杂度是 $O(L^2logL)$。
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
int main()
{
int A, B, L;
cin >> A >> B >> L;
int a, b;
double delta = 1e9;
for (int i = 1; i <= L; i ++ )
for (int j = 1; j <= L; j ++ )
if (gcd(i, j) == 1)
{
double x = i * 1.0 / j;
double X = A * 1.0 / B;
if (x >= X && x - X < delta)
{
delta = x - X;
a = i, b = j;
}
}
cout << a << ' ' << b << endl;
return 0;
}
假设(a
,b
)!=1那么一定有一组(a
,b
)=1且a/b
=a/b
满足上面的条件的都被扫过了
也就是说 gcd函数不用写了
将代码中的“if (x >= X && x - X < delta)” 改为“if (x > X && x - X < delta)”,“if (gcd(i, j) == 1)”删去
时间复杂度降到O(L^2)
感谢指点,题解已完善~
“if (x >= X && x - X < delta)” 不可改为“if (x > X && x - X < delta)”
改成if (x >= X && x - X < delta)