全部TLE了
查看原帖
全部TLE了
767269
AC_steve楼主2022/9/14 21:28

求助各位大佬,全部TLE了,到底是哪里出了问题

#include<iostream>
using namespace std;
int ans[1005],t[1005],h=2;
int cnt;
int gcd(int a,int b)
{
	if(b==0)return a;
	return gcdba,a%b);
}
void dfs(int rd,int m,int la,int lb)
{
	if(rd==h-1&&la!=1)return;
	if(la==1&&lb>m&&rd==h-1)
	{
		cnt=h;
		if(lb<ans[h]||ans[h]==0)
		{
			for(int i=1;i<=h-1;i++)ans[i]=t[i];
			ans[h]=lb;
		}
		return;
	}
	int x,y,tmp;
	int k=lb*(h-rd)/la;
	for(int i=m+1;i<=k;i++)
	{
		x=i*la-lb;
		y=i*lb;
		if(x<0)continue;
		tmp=gcd(x,y);
		x/=tmp;
		y/=tmp;
		t[rd+1]=i;
		dfs(rd+1,i,x,y);
	}
}
int main()
{
	int a,b;
	cin>>a>>b;
	int tmp=gcd(a,b);
	a/=tmp;
	b/=tmp;
	if(a==1)cout<<b;
	else
	{
		for(int h=2;;h++)
		{
			cnt=0;
			dfs(0,1,a,b);
			if(cnt)
			{
				for(int i=1;i<=cnt;i++)cout<<ans[i]<<' ';
				break; 
			}
		}
	}
	return 0;
}
2022/9/14 21:28
加载中...