Why WA?
  • 板块P1763 埃及分数
  • 楼主ZepX_D
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/4/9 10:15
  • 上次更新2024/4/9 16:12:07
查看原帖
Why WA?
464004
ZepX_D楼主2024/4/9 10:15
#include <bits/stdc++.h>
#define LL long long

using namespace std;

bool f;
int dep,s[10010],ans[10010];

void D(LL a,LL b,int p,int d)
{
	if(!a)
	{
		f = 1;
		for (int i = 1;i < d;i++)
			ans[i] = s[i];
	}
	if(d > dep || (f && p+1 >= ans[dep])) return ;
	LL dd = __gcd(a,b);
	a /= dd,b /= dd;
	for (LL i = max((LL)p+1,b/a);i <= 1e7;i++)
	{
		if(i*a < b) continue;
		if(a*i > b*(dep-d+1)) break;
		s[d] = i,D(a*i-b,b*i,i,d+1);
	}
}

int main()
{
	int a,b;cin >> a >> b;
	while(!f) ++dep,D(a,b,0,1);
	for (int i = 1;i <= dep;i++)
		cout << ans[i] << " ";
	return 0;
}
2024/4/9 10:15
加载中...