1 = 1/2 + 1/3 + 1/9 + 1/18
1 = 1/2 + 1/3 + 1/10 + 1/15
1 = 1/3 + 1/5 + 1/7 + 1/9 + 1/11 + 1/15 + 1/35 + 1/45 + 1/231

4

1/2 1/3 1/8 1/24
1/2 1/3 1/9 1/18
1/2 1/3 1/10 1/15
1/2 1/4 1/5 1/20
1/2 1/4 1/6 1/12

5

1/2 1/3 1/12 1/21 1/28
1/2 1/4 1/6 1/21 1/28
1/2 1/4 1/7 1/14 1/28
1/2 1/4 1/8 1/12 1/24
1/2 1/4 1/9 1/12 1/18
1/2 1/4 1/10 1/12 1/15
1/2 1/5 1/6 1/12 1/20
1/3 1/4 1/5 1/6 1/20

CPU消耗 < 2000ms

3个回答

`````` //c++ 要分母小于等于30的话 41行改成"if(a[n]>30)"
#include<cstdio>
#include<cstring>
#include<iostream>
#define MAXN 100

using namespace std;
long long a[MAXN+8],ans[MAXN+8],n;
bool find_ans;
long long gcd(long long a,long long b)
{
long long t;
while(b)
{
t=a%b;
a=b;
b=t;
}
return a;
}
bool better()
{
int i;
for(i=n;i>=0;i--)
{
if(a[i]==ans[i])
continue;
return (ans[i]==0||a[i]<ans[i]);
}
return 0;
}
void dfs(int cur,int s,long long fz,long long fm)
{
if(cur==n)
{
if(fm%fz)
return ;
a[cur]=fm/fz;/*
if(better())
memcpy(ans,a,sizeof(long long)*(n+1));*/
if(a[n]>=30)
return ;
for(int i=0;i<n;i++)
printf("1/%d ",(int)a[i]);
printf("1/%d\n",(int)a[n]);
return ;
}
s=(int)max(s*1LL,fm/fz+1);
int i;
long long A,B,Gcd;
for(i=s;;i++)
{
if((i*fz)>=(fm*(n-cur+1)))
break;
a[cur]=i;
B=fm*i;
A=fz*i-fm;
Gcd=gcd(A,B);
dfs(cur+1,i+1,A/Gcd,B/Gcd);
}
return ;
}
int main()
{
long long a,b;
//cin>>a>>b;
a=1,b=1;
cin>>n;
n--;
dfs(0,b/a+1,a,b);
return 0;
}
``````
SilentHeartDZ 大神能解释一下dfs函数吗？我看了N久没搞懂，求解啊，不胜感激！！！
5 年多之前 回复

C语言版的，只是稍微改了改

``````# include <stdio.h>
# include <string.h>
# include <stdlib.h>
# define MAXN 100

int max(int a,int b)
{
return a>b?a:b;
}

long long a[MAXN+8],ans[MAXN+8],n;
_Bool find_ans;
long long gcd(long long a,long long b)
{
long long t;
while(b)
{
t=a%b;
a=b;
b=t;
}
return a;
}
_Bool better()
{
int i;
for(i=n;i>=0;i--)
{
if(a[i]==ans[i])
continue;
return (ans[i]==0||a[i]<ans[i]);
}
return 0;
}
void dfs(int cur,int s,long long fz,long long fm)
{
if(cur==n)
{
int i;
if(fm%fz)
return ;
a[cur]=fm/fz;
if(a[n]>=30)
return ;
for(i=0;i<n;i++)
printf("1/%d ",(int)a[i]);
printf("1/%d\n",(int)a[n]);
return ;
}
s=(int)max(s*1LL,fm/fz+1);
int i;
long long A,B,Gcd;
for(i=s;;i++)
{
if((i*fz)>=(fm*(n-cur+1)))
break;
a[cur]=i;
B=fm*i;
A=fz*i-fm;
Gcd=gcd(A,B);
dfs(cur+1,i+1,A/Gcd,B/Gcd);
}
return ;
}
int main()
{
long long a,b;
//cin>>a>>b;
a=1,b=1;
scanf("%lld", &n);
n--;
dfs(0,b/a+1,a,b);
return 0;
}

``````