目录
问题 C: 埃及分数
题目描述
输入
输出
样例输入
样例输出
题解
本篇题解也发表于 http://zwcblog.top./zhouyukai/aijifenshu/ 作者是同一个人
问题 C: 埃及分数
题目描述
在古埃及, 人们使用单位分数的和 (形如 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.
输出
若干个数, 自小到大排列, 依次是单位分数的分母.
样例输入
19 45
样例输出
5 6 18
题解
这道题目就是个暴力
首先先抨击朱老师没有打 spj, 而此题需要 spj
例如:
- \(\frac{
- 59
- }{
- 211
- }=\frac{
- 1
- }{
- 4
- }+\frac{
- 1
- }{
- 36
- }+\frac{
- 1
- }{
- 633
- }+\frac{
- 1
- }{
- 3798
- }\)
- \(\frac{
- 59
- }{
- 211
- }=\frac{
- 1
- }{
- 6
- }+\frac{
- 1
- }{
- 9
- }+\frac{
- 1
- }{
- 633
- }+\frac{
- 1
- }{
- 3798
- }\)
而这两个答案都可以
我们从 1 开始枚举分母的个数, 然后我们假设当前分母为 \(\frac{a}{b}\)
前面分母的最大值为 \(t\) \(deepthset\) 表示分母的个数
\((max(t,\frac{b}{a})+1->\frac{b}{a}*(deepest-depth+1))-1\)
这样, 我们惊奇地发现, 当 \(n\),\(m\) 在 1000 以内时, 跑得非常快
于是这道题目就做完了, 时间复杂度......
代码
- #include <cstdio>
- #include <algorithm>
- #include <cstring>
- using namespace std;
- typedef long long LL;
- const int N=1020;
- LL ans[N],sum[N];
- int n,m,deepest;
- int gcd(int __m, int __n){
- while (__n != 0){
- int __t = __m % __n;
- __m = __n;
- __n = __t;
- }
- return __m;
- }
- LL gcd(LL __m, LL __n){
- while (__n != 0){
- LL __t = __m % __n;
- __m = __n;
- __n = __t;
- }
- return __m;
- }
- bool dfs(LL a,LL b,LL depth,LL t){
- if (depth==deepest){
- if ((b%a)!=0) return 0;
- ans[depth]=b/a;
- bool Flag=false;// 判断答案是否更优
- for (int i=depth;i>=0;--i){
- if (ans[i]!=sum[i]) {
- if (ans[i]<sum[i]) Flag=true;
- else Flag=false;
- break;
- }
- }
- if (Flag) {
- for (int i=0;i<=depth;++i)
- sum[i]=ans[i];
- }
- return 1;
- }
- bool flag=false;
- for (int i=max(t,b/a)+1;i<(b/a*(deepest-depth+1));++i){
- ans[depth]=i;
- if (dfs(a*i-b,b*i,depth+1,i)) flag=true;
- }
- return flag;
- }
- int main(){
- memset(sum,0x3f3f3f,sizeof(sum));
- scanf("%d%d",&n,&m);
- int Gcd=gcd(n,m);
- n/=Gcd,m/=Gcd;
- if (n==1){
- printf("%d\n",m);
- return 0;
- }
- for (int i=1;;++i){
- deepest=i;
- if (dfs(n,m,0,m/n)){
- for (int j=0;j<=i;++j)
- printf("%d%c",sum[j],j==i?'n':' ');
- break;
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2861043.html