求调(最后一点TLE)
查看原帖
求调(最后一点TLE)
1028934
KarlScvell楼主2023/11/28 21:15
#include<bits/stdc++.h>
#define int long long
using namespace std;
int gcd(int a,int b)
{
	if(b==0) return a;
	return gcd(b,a%b);
}
bool flag;
int cnt=1,sa,sb;
int ans[1001],ls[1001];
void dfs(int dep,int a,int b){
	if(dep==cnt){
		if(b%a) return;
		if(b/a==ls[dep-1]) return;
		flag=true;
		ls[dep]=b/a;
		if(ans[dep]>ls[dep]) memcpy(ans,ls,sizeof ls);
		return;
	}
	for(int i=max(b/a+1,ls[dep-1]+1);;i++){
		if(b*(cnt-dep+1)<a*i) break;
		ls[dep]=i;
		int aa=a*i-b,bb=b*i;
		int g=gcd(aa,bb);
		aa/=g,bb/=g;
		dfs(dep+1,aa,bb);
	}
}
signed main(void){
	cin>>sa>>sb;
	if(sb%sa==0){
		cout<<sb/sa;
		return 0;
	}
	int g=gcd(sa,sb);
	sa/=g,sb/=g;
	while(1){
		cnt++;
		ans[cnt]=0x3f3f3f3f;
		dfs(1,sa,sb);
		if(flag) break;
	}
	for(int i=1;i<=cnt;i++) cout<<ans[i]<<' ';
	return 0;
}
2023/11/28 21:15
加载中...