Project Eular-71-Ordered fractions

ACM模版

描述

题解

看到这个题，想到有一个叫做 Stern−Brocot$Stern-Brocot$ 树的东西，是专门用来拆分 0−1$0-1$ 所有真分数的，在《具体数学》上有讲，但是书没拿，也就能去仔细回顾一下了。

这个题只要答案，所以就算纯暴力也是可以搞定的，O(n2)$O(n^2)$ 枚举判断，不过这样不太优雅，所以考虑可以降低到 O(n)$O(n)$，因为我们要找小于 37$\frac{3}{7}$ 的最简分数中最大的那个，也就是取最大的 pq<37$\frac{p}{q}<\frac{3}{7}$，所以我们可以枚举 q$q$，然后令 p=⌊3q−17⌋$p=\lfloor \frac{3q-1}{7}\rfloor$，这样就可以保证是小于 37$\frac{3}{7}$，然后取最大即可。

最后结果为 428570999997$\frac{428570}{999997}$，但是提交了很多次都是错的，然后认识了一个单词叫做 numerator$numerator$。

代码

#include <iostream>

using namespace std;

/*
 *  428570/999997
 *  a/b 为 ans，初始 0/1
 *  设 p/q < 3/7，则 7p < 3q
 *  分母减小，7p < 3q - 1，则 p 最大为 floor((3q - 1) / 7)
 *  枚举 q，取小于 3/7 的最大 p/q 给 a/b
 */
void solve(int x, int y, int &a, int &b, int d)
{
    for (int q = 2; q <= d; q++)
    {
        int p = (int)((x * q - 1) / y);
        if (a * q < b * p)
        {
            a = p;
            b = q;
        }
    }
}

int main()
{
    int a = 0, b = 1, d = 1000000;
    int x = 3, y = 7;

    solve(x, y, a, b, d);

    printf("%d/%d\n", a, b);

    return 0;
}