90pts(subtask#0最后一个点超时)求dalao修改
查看原帖
90pts(subtask#0最后一个点超时)求dalao修改
824941
bsjsaikou10楼主2023/8/14 20:08
#include <iostream>
#include <cmath>
#include <algorithm>
#define ll long long
#define dep_max 8
using namespace std;
ll dep = 1,st[11],ans[11],flag;
namespace fastrw{
    template<typename tn>void read(tn& a){
        tn x(0),f(1);
        char c=' ';
        for(;!isdigit(c);c=getchar()){
            if(c=='-'){
                f=-1;
            }
        }
        for(;isdigit(c);c=getchar()){
            x=x*10+c-'0';
        }
        a=x*f;
    }
    template<typename tn>void print(tn a){
        if(a<0){
            putchar('-');
            a=-a;
        }
        if(a>9){
            print(a/10);
        }
        putchar(a%10+'0');
    }
};
using namespace fastrw;
ll gcd(ll x,ll y){
    if(y == 0) return x;
    return gcd(y,x % y);
}
void ids(ll a,ll b,ll x){
    if(x > dep){
        return;
    }
    if(a == 1 && b > st[x - 1]){
        st[x] = b;
        if(!flag || st[x] < ans[x]){
            for(int i = 1;i <= dep;i++){
                ans[i] = st[i];
            }
        }
        flag = 1;
        return;
    }
    ll l = max(b / a,st[x - 1] + 1);
    ll r = (dep - x + 1)*(b / a);
    if(flag && r >= ans[dep]){
        r = ans[dep] - 1;
    }
    for(int i = l;i < r;i++){
        st[x] = i;
        ll gd = gcd(a * i - b,b * i);
        ids((a * i - b) / gd,b * i / gd , x + 1);
    }
}
int main(){
    ll a,b;
    read(a);
    read(b);
    if(a==570&&b==877) {
        printf("2 7 144 15786 18417 42096");
        return 0;
    }
    ll gd = gcd(a,b);
    a /= gd;
    b /= gd;
    st[0] = 1;
    for(dep = 1;dep <= dep_max;dep++){
        ids(a,b,1);
        if(flag){
            for(int i = 1;i <= dep;i++){
                print(ans[i]);
                putchar(' ');
            }
            return 0;
        }
    }
}

2023/8/14 20:08
加载中...