• 洛谷P1763 埃及分数


    传送门

    题目描述

    来源:BIO 1997 Round 1 Question 3
    在古埃及,人们使用单位分数的和(形如 \dfrac{1}{a}
    a
    1

    的,aa 是自然数)表示一切有理数。如:\dfrac{2}{3} = \dfrac{1}{2} + \dfrac{1}{6}
    3
    2

    2
    1

    +
    6
    1

    ,但不允许 \dfrac{2}{3} = \dfrac{1}{3} + \dfrac{1}{3}
    3
    2

    3
    1

    +
    3
    1

    ,因为加数中有相同的。对于一个分数 \dfrac{a}{b}
    b
    a

    ,表示方法有很多种,但是哪种最好呢?首先,加数少的比加数多的好,其次,加数个数相同的,最小的分数越大越好。如:

    1945=13+112+1180 1945=13+115+145 1945=13+118+130 1945=14+16+1180 1945=15+16+118 " role="presentation" style="position: relative;">1945=13+112+1180 1945=13+115+145 1945=13+118+130 1945=14+16+1180 1945=15+16+118 

    45
    19

    45
    19

    45
    19

    45
    19

    45
    19

    =
    3
    1

    +
    12
    1

    +
    180
    1

    =
    3
    1

    +
    15
    1

    +
    45
    1

    =
    3
    1

    +
    18
    1

    +
    30
    1

    =
    4
    1

    +
    6
    1

    +
    180
    1

    =
    5
    1

    +
    6
    1

    +
    18
    1

    最好的是最后一种,因为 \dfrac{1}{18}
    18
    1

    比 \dfrac{1}{180}, \dfrac{1}{45}, \dfrac{1}{30}
    180
    1

    ,
    45
    1

    ,
    30
    1

    都大。
    注意,可能有多个最优解。如:

    59211=14+136+1633+13798 59211=16+19+1633+13798 " role="presentation" style="text-align: center; position: relative;">59211=14+136+1633+13798 59211=16+19+1633+13798 

    211
    59

    211
    59

    =
    4
    1

    +
    36
    1

    +
    633
    1

    +
    3798
    1

    =
    6
    1

    +
    9
    1

    +
    633
    1

    +
    3798
    1

    由于方法一与方法二中,最小的分数相同,因此二者均是最优解。

    给出 a,ba,b,编程计算最好的表达方式。保证最优解满足:最小的分数 \ge \cfrac{1}{10^7}≥
    10
    7

    1

    输入格式

    一行两个整数,分别为 aa 和 bb 的值。

    输出格式

    输出若干个数,自小到大排列,依次是单位分数的分母。

    输入输出样例

    输入 #1复制
    19 45
    输出 #1复制
    5 6 18

    说明/提示

    1 \lt a \lt b \lt 10001

    上代码:

    #include 
    #include 
    #include 
    
    #define LL long long
    #define MAXN 1010
    #define max(x,y) (x > y ? x : y)
    
    LL a, b, depth;
    bool flag;
    LL temp[MAXN], ans[MAXN];	// 分别记录当前答案与最终答案。
    
    LL gcd (LL x, LL y) {
        return (!y ? x : gcd (y, x % y));
    }	// 求最大公约数。
    
    void dfs (LL newa, LL newb, LL step) {
        if (step + 1 == depth) {
            if (newa == 1) {
                temp[step + 1] = newb;
                flag = true; 
                if (temp[depth] < ans[depth] || !ans[depth]) {
                    memcpy (ans, temp, sizeof (temp));
                }
            }
    
            return ;
        }
    
        LL first = newb % newa ? newb / newa + 1 : newb / newa;
        for (LL i = max (temp[step] + 1, first); i <= ceil (newb / newa) * (depth - step); i++) {
            temp[step + 1] = i;
            LL nxta, nxtb, g;
            nxta = newa * i - newb;
            nxtb = newb * i;
            g = gcd (nxta, nxtb);
            dfs (nxta / g, nxtb / g, step + 1);
        }
    }	// 搜索主体。
    
    int main (void) {
    
        scanf ("%d %d", &a, &b);
        LL g = gcd (a, b);
        temp[0] = 1;
    
        for (depth = 1; ; depth++) {
            dfs (a / g, b / g, 0);
            if (flag) { break ; }
        }
        for (int i = 1; i <= depth; i++) {
            printf ("%d ", ans[i]);
        }
    
        return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
  • 相关阅读:
    2022 年河南省大学生程序设计竞赛 个人题解
    每日一题:跳跃游戏II
    V100 GPU服务器安装CUDA教程
    李沐:用随机梯度下降来优化人生!
    安装依赖报错
    Python电梯楼层数字识别
    Spring整合Redis详细步骤
    现场感言讲稿的标准模板
    vue draggable学习
    财富通公司开发洗车小程序有哪些用处?
  • 原文地址:https://blog.csdn.net/lzx_xzl_______/article/details/126264209