NC50246. 埃及分数
描述
输入描述
一行两个整数，分别为a和b的值。
输出描述
输出若干个数，自小到大排列，依次是单位分数的分母。
示例1
输入:
19 45
输出:
5 6 18
C++(g++ 7.5.0) 解法, 执行用时: 354ms, 内存消耗: 484K, 提交时间: 2023-03-19 22:45:52
#include<bits/stdc++.h>
using namespace std;
long long a,b,c,de,flag=0,t[505],num[505];
long long gcd(long long x,long long y){
if(y==0) return x;
return gcd(y,x%y);
}
void dfs(long long a,long long b,long long k){
if(k>de||a<0) return;
if(a==1&&b>t[k-1]){
t[k]=b;
if(!flag||t[k]<num[k])
for(long long i=1;i<=k;i++) num[i]=t[i];
flag=1;
return;
}
long long r=b/a*(de-k+1);
if(flag&&num[de]<=r) r=num[de]-1;
for(long long i=max(t[k-1]+1,b/a);i<r;i++){
t[k]=i;
dfs((a*i-b)/gcd(a*i-b,b*i),b*i/gcd(a*i-b,b*i),k+1);
t[k]=0;
}
}
int main(){
cin>>a>>b;
c=gcd(a,b);
a/=c;
b/=c;
t[0]=1;
for(de=1;;de++){
dfs(a,b,1);
if(flag){
for(long long i=1;i<=de;i++) printf("%lld ",num[i]);
break;
}
}
return 0;
}
C++(clang++ 11.0.1) 解法, 执行用时: 243ms, 内存消耗: 424K, 提交时间: 2023-02-21 21:35:28
#include<bits/stdc++.h>
using namespace std;
long long a,b,c,de,flag=0,t[505],num[505];
long long gcd(long long x,long long y){
if(y==0) return x;
return gcd(y,x%y);
}
void dfs(long long a,long long b,long long k){
if(k>de) return;
if(a==1&&b>t[k-1]){
t[k]=b;
if(!flag||t[k]<num[k])
for(long long i=1;i<=k;i++) num[i]=t[i];
flag=1;
return;
}
long long r=b/a*(de-k+1);
if(flag&&num[de]<=r) r=num[de]-1;
for(long long i=max(t[k-1]+1,b/a);i<r;i++){
t[k]=i;
dfs((a*i-b)/gcd(a*i-b,b*i),b*i/gcd(a*i-b,b*i),k+1);
t[k]=0;
}
}
int main(){
cin>>a>>b;
c=gcd(a,b);
a/=c;
b/=c;
t[0]=1;
for(de=1;;de++){
dfs(a,b,1);
if(flag){
for(long long i=1;i<=de;i++) printf("%lld ",num[i]);
break;
}
}
return 0;
}