所有Hack都TLE求条
查看原帖
所有Hack都TLE求条
1094797
Myl100313楼主2025/7/28 22:08

代码如下:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b;
ll ans[114514],v[114514];
bool t;
ll gcd(ll x,ll y)
{
	if(y==0) return x;
	  else return gcd(y,x%y);
}
ll getf(ll x,ll y)
{
	return (y+x-1)/x;
}
bool check(int d)
{
	for(int i=d;i>=0;i--)
	  if(v[i]!=ans[i])
	    return ans[i]==-1||v[i]<ans[i];
	return false;
}
void dfs(int dep,int maxx,ll from,ll a1,ll b1)
{
	if(dep==maxx)
	{
		if(b1%a1) return ;
		v[dep]=b1/a1;
		if(v[dep]<=v[dep-1]) return ;
		if(check(dep))
		  memcpy(ans,v,sizeof (ll)*(dep+1));
		t=true;
		return ;
	}
	from=max(from,getf(a1,b1));
	for(ll i=from; ;i++)
	{
		if(b1*(maxx-dep+1)<=i*a1) break;
		v[dep]=i;
		ll a2=a1*i-b1;
		ll b2=b1*i;
		ll gc=gcd(a2,b2);
		dfs(dep+1,maxx,i+1,a2/gc,b2/gc);
	}
}
void you_and_idol()
{
	t=false;
	for(int i=1;i<=114514;i++)
	{
		memset(ans,-1,sizeof ans);
		dfs(0,i,getf(a,b),a,b);
		if(t)
		{
			for(int j=0;j<=i;j++)
			  cout<<ans[j]<<" ";
			cout<<endl;
			return ;
		}
	}
}
int main()
{
	//ios::sync_with_stdio(0);
	//cin.tie(nullptr);
	cin>>a>>b;
	you_and_idol();
	return 0;
}

所有正式数据AC,所有Hack数据TLE

2025/7/28 22:08
加载中...