题解

1 条题解

  • 0
    @ 2022-08-13 22:04:00
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <cmath>
    #include <iostream>
    #include <algorithm>
    #define N 1000
    using namespace std;
    
    long long ans[N], s[N], mo, ch;
    int dep;
    long long gcd(long long a, long long b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    void outp() {
        int i;
    
        if (ans[dep] > s[dep]) {
            for (i = 1; i <= dep; i++) {
                ans[i] = s[i];
            }
        }
    }
    void dfs(long long x, long long y, int d) {
        long long a, b, i, w;
    
        if (d == dep) {
            s[d] = y;
    
            if ((x == 1) && (s[d] > s[d - 1]))
                outp();
    
            return;
        }
    
        //s[d-1]是上一层搜到的分母,这一层分母至少是s[d-1]+1,另外
        //当前的剩余分数是x/y,所以接下来枚举的分数至少是y/x+1
        //所以i的初值是在两者间取最大值
        //i<(dep-d+1)*y/x是因为(dep-d+1)*(1/i)肯定会大于剩余的分数 x/y
        for (i = max(s[d - 1] + 1, y / x + 1); i < (dep - d + 1)*y / x; i++) {
            //        b=y*i/gcd(y,i);//b是分母,并且是等于通分后的分母
            //        a=b/y*x-b/i;//a是分子
            //        w=gcd(a,b);
            //        a/=w;
            //        b/=w;
    
            a = x * i - y;
            b = y * i;
            w = gcd(a, b);
            a /= w;
            b /= w;
            s[d] = i;
            dfs(a, b, d + 1);
        }
    }
    int main() {
        int i = 0, j;
        scanf("%lld%lld", &ch, &mo);
        i = gcd(ch, mo);
        ch /= i;
        mo /= i;
    
        for (dep = 2;; dep++) {
            ans[1] = 0;
            s[0] = 0;
            ans[dep] = 2000000000;
            dfs(ch, mo, 1);
    
            if (ans[1] != 0)
                break;
        }
    
        for (j = 1; j <= dep; j++) {
            printf("%lld ", ans[j]);
        }
    
        printf("\n");
        return 0;
    }
    
    /*
    我们用dep限制搜索层数,先从2开始,每次深度+1
    
      搜索时每一层比上一层的分数小,即分母一次比一次大
    
      每次枚举出 1/a 后,用当前分数减去,然后递归传递剩余的分数
    
      每层搜索枚举的限制条件:
    
        1、保证当前深度分母大于上一深度分母
    
        2、枚举的1/a小于当前分数,不可能存在等于的状态,因为此种最优解会在限制深度较小的时候出现
    
        3、设当前剩余分数为x/y,剩余深度为d,则 x/y<d/a → a<d/x*y。
    
           不妨先设之后枚举的分母都为 a,那么最后也就刚好达到 x/y ,但又因分数不能相等,所以 a 必须小于该值,即把分数调大。如果分数很小,那么就永远够不着目标分数
    
      当深度达到限制深度时,只需判断剩余的分数是否满足1/a的形式,然后更新结果
    
      记得开long long ,使用%lld输出,因为通分的时候数据会很大
    
      时间复杂度和搜索大致一致,因为当前限制深度的时间复杂度远大于上一次限制深度的时间复杂度,所以之前深度的时间可以忽略
    
      优点是空间开支特别小
    */
    
  • 1

信息

ID
1508
难度
11
分类
搜索 点击显示
标签
递交数
1
已通过
1
通过率
100%
上传者