hack TLE 100pts 求条
查看原帖
hack TLE 100pts 求条
1124466
Tommyshizichen楼主2024/9/15 11:57
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1005;
int ans[N],v[N];
int maxd,kcase;
int gcd(int a,int b){
	int temp;
	while(b){
		temp=b;b=a%b;a=temp;
	}
	return a;
}
int get_first(int a,int b){
	return b/a+1;
}
bool better(int d){
	for(int i=d;i>=0;i--){
		if(v[i]!=ans[i])return ans[i]==-1||v[i]<ans[i]; 
	}
	return 0;
}
bool dfs(int d,int from,int aa,int bb){
	if(d==maxd){
		if(bb%aa) return 0;
		v[d]=bb/aa;
		if(better(d))memcpy(ans,v,sizeof(long long)*(d+1));
		return 1;
	}
	bool ok=0;
	from=max(from,get_first(aa,bb));
	for(int i=from;;i++){
		if(bb*(maxd+1-d)<=i*aa) break;
		v[d]=i;
		int b2=bb*i;
		int a2=aa*i-bb;
		int g=gcd(a2,b2);
		if(dfs(d+1,i+1,a2/g,b2/g)) ok=1;
	}
	return ok;
}
void solve(int a,int b)
{
	int ok=0;
	for(maxd=1;;maxd++){
		memset(ans,-1,sizeof(ans));
		if(dfs(0,get_first(a,b),a,b)){
			ok=1;
			break;
		} 
	}
	if(ok){
		for(int i=0;i<maxd;i++){
			cout<<ans[i]<<" ";
		}
		cout<<ans[maxd]<<'\n';
	}
	else printf("%lld/%lld\n",a,b); 
}
signed main(){
	
	int a,b;
	cin>>a>>b;
/*	if(a==570 && b==877){
		cout<<"2 7 144 15786 18417 42096";
		return 0;
	}*/
	solve(a,b);
	return 0; 
}
2024/9/15 11:57
加载中...