题解 | #将真分数分解为埃及分数#

将真分数分解为埃及分数

http://www.nowcoder.com/practice/e0480b2c6aa24bfba0935ffcca3ccb7b

题意

给定一个小于1的分数，拆分成分母互不相等，分子为1的分数的和

方法

让分子单调递减

真要拆分，根据等差数列求和公式可以无限拆分。

而这里肯定希望是有限拆分，说到有限，又观察到这分子分母始终是整数，整数具有离散性，所以考虑能否利用整数的离散性来保证有限

对于分母和分子最大公约数不为1的，把分子和分母同时除以这个公因数。

剩下我们考虑的，全部是分子分母互质。

若当前 分子/分母 为 a/b, (a<b)

因为互质性，显然存在 k使得(k-1)a < b < ka

那么有ka-b < ka-(k-1)a = a

因此 $\frac{a}{b} = \frac{ka}{kb} = \frac{ka-b+b}{kb} = \frac{ka-b}{kb} + \frac{b}{kb} = \frac{ka-b}{kb} + \frac{1}{k}$

这里

拆除的了分母为k分子为1的分数
剩余部分的分子ka-b小于原来的分子a

这样的拆分方法，保证了能在有限次数内完成拆分

注意，对于拆分出的 $\frac{ka-b}{kb}$ 在下轮拆分时，依然需要先处理公约数

以题目 8/11 为例子

a	b	k	变化
8	11	2	$a = 2 * 8 - 11 = 5, b = 2 * 11 = 22$ , 产出1/2
5	22	5	$a = 5 * 5 - 22 = 3, b = 22 * 5 = 110$ , 产出1/5
3	110	37	$a = 37 * 3 - 110 = 1, b = 110 * 37 = 4070$ , 产出1/37
1	4070	-	分子是1，直接产出

所以输出为1/2+1/5+1/37+1/4070

代码

#include<bits/stdc++.h>
using namespace std;
long long gcd(long long a,long long b){
    return b==0?a:gcd(b,a%b);
}

int main(){
    long long a,b;
    while (~scanf("%lld/%lld",&a,&b)){
        long long c = gcd(a,b);
        a/=c;
        b/=c;
        vector<long long> fm;
        while(a > 1){ // 分子为1 直接输出
            // a/b => b/kb + (ka-b)/kb = 1/k + (ka-b)/kb
            int k;
            for(k = 1;k*a<b;k++); // 找到满足 (k-1)a < b < ka 的 k
            fm.push_back(k);
            a = a*k-b; // 计算 新的 a,b
            b = k*b;
            long long m = gcd(a,b);
            a/=m;
            b/=m;
        }
        fm.push_back(b);
        sort(fm.begin(),fm.end());
        printf("1/%d",fm[0]);
        for(int i = 1;i<fm.size();i++){
            printf("+1/%lld",fm[i]);
        }
        printf("\n");
    }
    return 0;
}

复杂度分析

设初始分子为n, 结果最大分母为m

时间复杂度: 注意到分母在过程中成倍增长，而同时分子在减小，每轮计算次数约为分母除以分子，所以时间复杂度为 $O (m)$

空间复杂度: 用了vector来记录结果，而因为保证分子严格递减，vector的长度不大于分子，所以空间复杂度为 $O (n)$

数学优化计算

在上面，我们从数学上证明了k的存在性，并通过遍历去找到k

注意到(k-1)a < b < ka, 可以变形

$k-1 < \frac{b}{a} < k$ 所以 $k = \lfloor\frac{b}{a} \rfloor +1 \ge 2$

同时，这里也表明 $\frac{kb}{ak-b} > \frac{kb}{k\frac{b}{k-1} - b} = \frac{kb}{\frac{b}{k-1}} = k(k-1) \ge k > \frac{b}{a}$

说明了产生的k越来越大,互不相等

代码

#include<bits/stdc++.h>
using namespace std;
long long gcd(long long a,long long b){
    return b==0?a:gcd(b,a%b);
}

int main(){
    long long a,b;
    while (~scanf("%lld/%lld",&a,&b)){
        long long c = gcd(a,b);
        a/=c;
        b/=c;
        vector<long long> fm;
        bool first = true; // 首次输出
        while(a > 1){
            // a/b => b/kb + (ka-b)/kb = 1/k + (ka-b)/kb
            // k-1 < b/a < k 替代掉遍历查找
            int k = b/a+1;
            if(!first){
                printf("+");
            }else{
                first = false;
            }
            printf("1/%d",k);
            a = a*k-b;
            b = k*b;
            long long m = gcd(a,b);
            a/=m;
            b/=m;
        }
        if(!first){
            printf("+");
        }else{
            first = false;
        }
        printf("1/%d",b);
        printf("\n");
    }
    return 0;
}