【求助】WA 40pts
查看原帖
【求助】WA 40pts
255077
麦克斯韦の妖楼主2022/5/24 21:10
#include<cstdio>
#include<iostream> 
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll; 
// IDA*
const int N=1e3+10;
ll a,b,k;
ll M;
ll ans[N];
ll tmp[N];
inline ll Max(ll x,ll y)
{
	return x>y ? x : y;
}
ll gcd(ll x,ll y)
{
	if(x%y==0) return y;
	else if(x<y) gcd(y,x);
	else gcd(y,x%y);
}
inline ll getP(ll x,ll y)   
{
	return y/x+1;
}
void change(ll d)
{
	int flag=1;
	for(ll i=d;i>=1;i--)
	{
		if(ans[i]==-1) 
		{
			flag=0;
			break;
		}
		if(tmp[i]<ans[i])
		{
			flag=0;
			break;
		}
	}
	if(flag==0)
	{
		for(ll i=1;i<=d;i++)
		{
			ans[i]=tmp[i];
		}
	}
}
bool DFS(ll d,ll h,ll x,ll y) 
{
	if(d==M)
	{
		if(y%x) return false;
		tmp[d]=y/x;
		change(d);
		return true;
	}
	bool ok=false;
	h=Max(h,getP(x,y));
	for(ll i=h; ;i++)
	{
		if(y*(M+1-d) <= x*i) break;	//h(x)剪枝 
		tmp[d]=i;
		if(DFS(d+1,i+1,(x*i-y)/gcd(x*i-y,y*i),y*i/gcd(x*i-y,y*i))) ok=true;
	}
	return ok;
}
int main()
{
	scanf("%lld%lld",&a,&b);
	for(M=2; ;M++)
	{
		memset(ans,-1,sizeof(ans));
		if(DFS(1,getP(a,b),a,b)) break;
	}
	for(int i=1;i<=M;i++)
	{
		printf("%lld ",ans[i]);
	}
	return 0;
} 
2022/5/24 21:10
加载中...