I don't know how to do that fucking things.
埃及分数
题目描述
来源：BIO 1997 Round 1 Question 3
在古埃及，人们使用单位分数的和（形如 \(\dfrac{1}{a}\) 的，\(a\) 是自然数）表示一切有理数。如：\(\dfrac{2}{3} = \dfrac{1}{2} + \dfrac{1}{6}\)，但不允许 \(\dfrac{2}{3} = \dfrac{1}{3} + \dfrac{1}{3}\)，因为加数中有相同的。对于一个分数 \(\dfrac{a}{b}\)，表示方法有很多种，但是哪种最好呢？首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好。如：
\[\begin{aligned} \frac{19}{45} &= \frac{1}{3} + \frac{1}{12} + \frac{1}{180}\\ \frac{19}{45} &= \frac{1}{3} + \frac{1}{15} + \frac{1}{45}\\ \frac{19}{45} &= \frac{1}{3} + \frac{1}{18} + \frac{1}{30}\\ \frac{19}{45} &= \frac{1}{4} + \frac{1}{6} + \frac{1}{180}\\ \frac{19}{45} &= \frac{1}{5} + \frac{1}{6} + \frac{1}{18}\\ \end{aligned} \]最好的是最后一种，因为 \(\dfrac{1}{18}\) 比 \(\dfrac{1}{180}, \dfrac{1}{45}, \dfrac{1}{30}\) 都大。
注意，可能有多个最优解。如：
由于方法一与方法二中，最小的分数相同，因此二者均是最优解。
给出 \(a,b\)，编程计算最好的表达方式。保证最优解满足：最小的分数 \(\ge \cfrac{1}{10^7}\)。
输入格式
一行两个整数，分别为 \(a\) 和 \(b\) 的值。
输出格式
输出若干个数，自小到大排列，依次是单位分数的分母。
样例 #1
样例输入 #1
19 45
样例输出 #1
5 6 18
提示
\(1 \lt a \lt b \lt 1000\)
上代码（附解释）
/*
在古埃及，人们使用单位分数的和(形如1/a的, a是自然数)表示一切有理数。
如：2/3=1/2+1/6,但不允2/3=1/3+1/3,因为加数中有相同的。
对于一个分数a/b,表示方法有很多种，但是哪种最好呢？
首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越 好。
如： 19/45=1/3 + 1/12 + 1/180
19/45=1/3 + 1/15 + 1/45
19/45=1/3 + 1/18 + 1/30
19/45=1/4 + 1/6 + 1/180
19/45=1/5 + 1/6 + 1/18.
最好的是最后一种，因为1/18比1/180,1/45,1/30,1/180都大。 给出a,b(0<a<b<1000),编程计算最好的表达方式
*/
/*
in:
19 45
out:
5 6 18
*/
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#define ll long long
#include <algorithm>
using namespace std;
#define endl "\n"
//depth:最多允许的层数，temp:边搜边存结果
//ans:存储最优解(擂主)
ll depth,temp[1001],ans[1001];
bool flag=0;
ll gcd(ll a,ll b) {
return b==0?a:gcd(b,a%b);
}
//分子是a，分母是b 递归树层数step
void dfs(ll a,ll b,ll step) {
if (step==depth) {
if (a==1) { //最后一个分子是1
temp[step]=b;
//最后一个分母第一次赋值(搜索到第一个可行解)，或者比之前的分母小，更新答案
if (ans[step]==0||temp[step]<ans[step]){
flag=1;
copy(temp,temp+depth+1,ans);
}
}
//无论是否成立，都必须return，不然就超过递归树的层数
return;
}
ll first=b%a!=0?b/a+1:b/a;
//起始值要么是上一个数字+1，要么是ceil(b/a)
int st=max(temp[step-1]+1,first);
//终点是分母允许的最大值(考虑剩余层数)
int ed=(b/a)*(depth-step+1);
// if(depth==3&&a==19&&b==45){
// cout<<"调试信息:";
// cout<<st<<" "<<ed<<endl;
// }
for(ll i=st; i<=ed; i++) {
temp[step]=i;
ll nexta,nextb,g;
//分数的减法，nextb为通分的值
//a/b - 1/i
//a*i/b*i - b/b*i
nexta=a*i-b,nextb=b*i;
g=gcd(nexta,nextb);//求gcd便于约分
dfs(nexta/g,nextb/g,step+1);
}
}
int main() {
ll a,b;
cin>>a>>b;
ll g=gcd(a,b);
temp[0]=1;
for(depth=1;depth<=b; depth++) {
memset(ans,0,sizeof(ans));
dfs(a/g,b/g,1);
if (flag) break;
}
for(int i=1; i<=depth; i++)
printf("%lld ",ans[i]);
return 0;
}
how to do that？
https://www.luogu.com.cn/record/141385042 get 100 but unaccepted
https://www.luogu.com.cn/record/105330451 get 100 and accepted
正解
https://www.luogu.com.cn/problem/solution/P1763
标签：分数,frac,P1763,dfrac,ll,45,19,hack,Unaccepted From： https://www.cnblogs.com/WYX1210/p/17936172.html