代码求解释
查看原帖
代码求解释
1278786
lihaoyyy楼主2024/2/23 11:52
#include<bits/stdc++.h>
using namespace std;

long long t[510],dep,flag;
long long ans[510];
bool check()
{
    if(ans[dep]==0||t[dep]<ans[dep])return true;
    return false;
}
long long gcd(long long a,long long b)
{
    if(b==0)return a;
    return gcd(b,a%b);
}
void dfs(int p,long long la,long long lb)
{
    if(p==dep)
    {
        if(lb%la==0)
        {
            t[p]=lb/la;
            if(check())
                memcpy(ans,t,sizeof(t));
            flag=1;
        }
        return;
    }
    for(long long  i=max((long long)t[p-1]+1,lb/la+1);la*i<lb*(dep-p+1);i++)
    {
        t[p]=i;
        long long nb=(long long)lb*i;
        long long na=(long long)la*i-lb;
        long long g=gcd(nb,na);
        dfs(p+1,na/g,nb/g);
    }
}
int main()
{
    int a,b;
    cin>>a>>b;
    for(dep=2;;dep++)
    {
        flag=0;
        dfs(1,a,b);
        if(flag)
        {
            for(int i=1;i<=dep;i++)
                printf("%d ",ans[i]);
            break;
        }
    }

    return 0;
}
2024/2/23 11:52
加载中...