Project Eular-71-Ordered fractions

ACM模版

描述

题解

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

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

最后结果为 428570999997 428570 999997 ，但是提交了很多次都是错的，然后认识了一个单词叫做 numerator n u m e r a t o r 。

代码

#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;
}