埃及分数 subtask TLE 求助
查看原帖
埃及分数 subtask TLE 求助
246331
mystic_qwq楼主2024/1/17 21:57
#define ll long long
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
a,b,d;
ll v[11],ans[11],gc;
void dfs(ll a,ll b,int k){
  if(a==1&&b>v[k-1]&&(ans[k]==0||b<ans[k])){
    memcpy(ans+1,v+1,8*(k-1)),ans[k]=b;return;
  }
  if(k==d)return;
  const ll l=max(b/a+1,v[k-1]+1),
  r=ans[d]?min(b*(d-k+1)/a,ans[d]-1-d+k):b*(d-k+1)/a;
  for(int i=l;i<=r;++i){
    v[k]=i,gc=gcd(a*i-b,b*i),dfs((a*i-b)/gc,b*i/gc,k+1);
  }
}
main(){
  scanf("%d%d",&a,&b),gc=gcd(a,b),a/=gc,b/=gc;
  for(d=1;d<=10;++d){
    dfs(a,b,1);
    if(ans[d]){
      for(int i=1;i<=d;++i) printf("%ld ",ans[i]);
      return 0;
    }
  }
}


2024/1/17 21:57
加载中...