求调P1763
  • 板块学术版
  • 楼主__galaxy_1202__
  • 当前回复6
  • 已保存回复6
  • 发布时间2024/9/8 21:20
  • 上次更新2024/9/9 12:51:18
查看原帖
求调P1763
1020835
__galaxy_1202__楼主2024/9/8 21:20

hack点没过,讨论区的大佬们讲的看不懂,能把我的代码改对的得一关

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll a, b, gcd, dep, num[11], ans[11];
bool can;
void dfs(ll a, ll b, ll x)
{
    if (x > dep) return;
    if (a == 1 && b > num[x - 1])
    {
        num[x] = b;
        if (can == 0 || num[x] < ans[x])
            for (int i = 1; i <= dep; i++)
                ans[i] = num[i];
        can = 1;
        return;
    }
    ll l = max(b / a, num[x - 1] + 1), r = (dep - x + 1) * b / a;
    if (can && r >= ans[dep]) r = ans[dep] - 1;
    for (ll i = l; i < r; i++)
    {
        num[x] = i;
        ll tmp = __gcd(a * i - b, b * i);
        dfs((a * i - b) / tmp, (b * i) / tmp, x + 1);
    }
}
int main()
{
    cin >> a >> b;
    gcd = __gcd(a, b);
    a /= gcd, b /= gcd;
    num[0] = 1;
    for (dep = 1; dep <= 10; dep++)
    {
        dfs(a, b, 1);
        if (can)
        {
            for (int i = 1; i <= dep; i++) cout << ans[i] << ' ';
            break;
        }
    }
    return 0;
}
2024/9/8 21:20
加载中...