题解 | #将真分数分解为埃及分数#
将真分数分解为埃及分数
http://www.nowcoder.com/practice/e0480b2c6aa24bfba0935ffcca3ccb7b
令
其中
且q,s都是非负整数；
左右两边同时除以)
得
也即
再对%7D)
当成
进行重复操作，直到
注意要对先约分；
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//辗转法
void Egypt(int a,int b,vector<int> &_rs)
{
while(a!=1)
{
//先约分
int gcd=__gcd(a,b);
a=a/gcd;
b=b/gcd;
int q=b/a;
_rs.push_back(1+q);
a=a-b%a;
b=b*(1+q);
}
_rs.push_back(b);
}
int main()
{
int a=0,b=0;
char ch='/';
while(cin>>a>>ch>>b)
{
vector<int> rs;
Egypt(a,b,rs);
for(int i=0;i<rs.size()-1;++i)
{
printf("1/%d+",rs[i]);
}
printf("1/%d\n",rs.back());
}
return 0;
}
