萌新刚学OI为何RE
  • 板块P1763 埃及分数
  • 楼主0Io_oI0
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/12/14 23:01
  • 上次更新2024/12/15 10:27:32
查看原帖
萌新刚学OI为何RE
1037440
0Io_oI0楼主2024/12/14 23:01
#include<bits/stdc++.h>
#define I using
#define AK namespace
#define IOI std
#define i_ak return
#define ioi  0
I AK IOI;
typedef long long ll;
ll a,b,d,v[10000005],ans[10000005];bool flag;
void dfs(ll a,ll b,ll deep){
	if(deep==d){
		if(b%a)return;
		if(b/a==v[deep-1])return;
		flag=1;
		v[deep]=b/a;
		bool cmp=0;
		for(int k=deep;k>=1;k--){
			if(ans[k]==v[k])continue;
			if(ans[k]<v[k])break;
			else{
				cmp=1;
				break;
			}
		}
		if(cmp)memcpy(ans,v,sizeof(ll)*(deep+1));
		return;
	}
	for(int k=max(b/a+1,v[deep-1]+1);;k++){
		if(b*(d-deep+1)<a*k)break;
		v[deep]=k;
		ll b2=b*k;
		ll a2=a*k-b;
		b2/=__gcd(a2,b2);
		a2/=__gcd(a2,b2);
		dfs(a2,b2,deep+1);
	}
}
int main(){
	cin>>a>>b;
	a/=__gcd(a,b),b/=__gcd(a,b);
	if(a==1){
		cout<<b;
		return 0;
	}
	for(int d=2;;d++){
		ans[1]=0;
		ans[d]=0x3f3f3f3f;
		dfs(a,b,1);
		if(flag)break;
	}
	for(int i=1;i<=d;i++)cout<<ans[i]<<' ';
	i_ak ioi;
}

本地测不输出,dalao 求调

2024/12/14 23:01
加载中...