90分求助!
  • 板块P1763 埃及分数
  • 楼主fanke
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/10/1 17:45
  • 上次更新2023/10/27 09:20:05
查看原帖
90分求助!
547120
fanke楼主2022/10/1 17:45
#include<bits/stdc++.h>
using namespace std;
long long gcd(long long x , long long y)
{
    if(y == 0)
        return x;
    return gcd(y , (x % y));
}
long long a , b , mt;
long long ans[10005] , num[10005];
bool flag = 0;
long long t = 0 , sum = 0;
void dfs(long long a, long long b, long long d, long long mt)
{
    if(d > mt) return ;
    long long ma = gcd(a, b);
    a /= ma;
    b /= ma;
    if(b % a == 0 && (b / a) > ans[d - 1])
    {
        ans[d] = b;
        if(!flag || ans[d] < num[d])
        {
            for(long long i = 1; i <= d; i ++)
                num[i] = ans[i];
            flag = 1;
            sum = d; 
        }
        return ;
    }
    long long s = b / a + 1;
    if(s <= ans[d - 1])
        s = ans[d - 1] + 1;
    long long t = (mt - d + 1) * (b / a);
    if(flag && t >= num[d]) 
        t = num[d] - 1; 
    for(long long i = s; i <= t; i ++)
    {
        ans[d] = i;
        dfs(a * i - b , b * i, d + 1, mt);  
    }
}
int main() 
{
    cin >> a >> b;
    for(long long i = 1 ; i <= a ; i ++)
    {
        flag = 0;
        dfs(a , b , 1 , i);
        if(flag == 1)
        {
            for(long long j = 1; j <= sum ; j ++)
            {
                printf("%lld ", num[j]);
            }
            return 0;
        }
    }
    return 0;
}
2022/10/1 17:45
加载中...