求助!
查看原帖
求助!
1447600
YuZhiBoAsuka楼主2024/12/22 10:17
#include<bits/stdc++.h>
using namespace std;
int a,b;
int deep;
int ans[102];
int anns[102];//预测深度
int find(int a,int b)
{
	for(int i=1;; i++)
		if(a*i>b) return i;
}
bool dfs(int d,int a,int b)
{
	if(d==deep)
	{
		if(b%a!=0)
			return 0;
		ans[d]=b/a;
		if(ans[d]<anns[d]||anns[d]==0) for(int i=0; i<=deep; i++) anns[i]=ans[i];
		return 1;
	} //达到目标深度
	int p=find(a,b);
	if(d>0)
		p=max(p,ans[d-1]+1);
	bool f=0;
	for(;; p++)
	{
		if((deep+d-1)*b<=p*a) break;
		ans[d]=p;
		int aa=a*p-b;
		int bb=b*p;
		int g=__gcd(aa,bb);
		if(dfs(d+1,aa/g,bb/g))
			f=1;
	}
	return f;
}
int main()
{
	scanf("%d%d",&a,&b);
	for(deep=1;; deep++)
	{
		if(dfs(1,a,b))
		{
			//找到答案了
			for(int i=1; i<=deep; i++) cout<<anns[i]<<' ';
			return 0;
		}
	}
	return 0;
}
2024/12/22 10:17
加载中...