哇了两个点,实在找不出哪里问题(7和10)
  • 板块P1763 埃及分数
  • 楼主ypyxc
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/10/9 13:10
  • 上次更新2023/10/27 08:06:37
查看原帖
哇了两个点,实在找不出哪里问题(7和10)
727723
ypyxc楼主2022/10/9 13:10
#include<iostream>
#include<string.h>
#include<algorithm>
#include <stdlib.h>
using namespace std;
int get_y(int x, int y)
{
	if (x % y == 0)
		return y;
	return get_y(y, x % y);
}
int deepth;
int way[50];
int reway[50];
bool is_ok = 0;
void dfs(int cur, int pre, int a, int b)
{
	if (cur == deepth)
	{
		if (a == 1)
		{
			if ((!is_ok) || (is_ok&&reway[cur] > b))
			{
				way[cur] = b;
				memcpy(reway,way,sizeof(way));
				is_ok = 1;
			}
		}
			return;
	}
	for (int f = pre + 1;; f++)
	{
		if (b * (deepth - cur + 1) <= a * f)
			break;
		way[cur] = f;
       if(a*f<b)
          continue;
		int newa = a * f - b;
		int newb = b * f;
		int te = get_y(newa,newb);
		dfs(cur + 1,f,newa/te,newb/te);
	}

}
int main()
{
	int a, b;
	cin >> a >> b;

	int te = get_y(a,b);
	a /= te; b /= te;
	for (deepth = 1;; deepth++)
	{
		dfs(1,1,a,b);
		if(is_ok)
		break;
	}
	for (int i = 1; i <= deepth; i++)
		cout << reway[i] << " ";
	return 0;
}

2022/10/9 13:10
加载中...