学步园

这题有很经典的方法，可以参见杨哲07年的文章。

我用的则是很直观的方法，枚举分母，然后二分分子。注意比较的时候尽量别用浮点，尽管调整精度可以AC。

 

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 typedef long long LL;
 7 
 8 int a, b;
 9 int c, d;
10 
11 inline LL labs(LL x)
12 {
13     return x < 0 ? -x : x;
14 }
15 
16 inline bool better(int a1, int b1, int a2, int b2)
17 {
18     return labs((LL)b * a1 * b2 - (LL)a * b1 * b2)
19          < labs((LL)b * a2 * b1 - (LL)a * b2 * b1);
20 }
21 
22 int main()
23 {
24     scanf("%d%d", &a, &b);
25     c = 1;
26     d = 1;
27     for (int i = 1; i <= 32767; i++)
28     {
29         int lf = 1, rt = 32767, mid;
30         while (lf + 1 < rt)
31         {
32             mid = lf + rt >> 1;
33             better(lf, i, rt, i) ? rt = mid : lf = mid;
34         }
35         mid = better(lf, i, rt, i) ? lf : rt;
36         int gcd = __gcd(mid, i);
37         if (mid / gcd == a && i / gcd == b)
38         {
39             if (mid == 1) mid++;
40             else mid--;
41         }
42         if (better(mid, i, c, d))
43         {
44             c = mid;
45             d = i;
46         }
47     }
48     printf("%d %d\n", c, d);
49 //    system("pause");
50     return 0;
51 }
52