/ Vijos / 题库 / 迷宫 /

题解

2 条题解

  • 1
    @ 2023-07-12 17:43:45
    #include<bits/stdc++.h>
    #define LL __int128
    using namespace std;
    LL gcd(LL x,LL y){return y?gcd(y,x%y):x;}
    LL sol(LL l,LL m,LL k){
        LL d=gcd(m,k);
        if (d==1) return l;
        if (l>k/d) return m*(k-l)/d+sol((k-m*(k-l))/d,m,k/d);
        return l;
    }
    int T;LL m,k;
    signed main () {
        scanf("%d",&T);
        while (T--) {
            scanf("%lld %lld",&m,&k);
            printf("%lld\n",sol(k-1,m,k)+1);
        } return 0;
    }
    
  • -1
    @ 2020-04-30 18:33:40
      我们发现自动机的平凡上界就是T。
    
       因为我们令到每一个点的路径在mo T意义下相等,则这样一定是合法的。
    
      我们考虑如何合并这些点:
    
      我们发现在 当两个点可以到达的点是一致的时候,就可以缩为一个点。
    
      我们发现*k mo T 相同就可以缩点。
    
      我们发现这样子是过不了的。
    
       因为我们其实缩点以后,我们划归为了一个子问题,所以我们要迭代下去。
    
       我们怎么迭代呢,我们考虑缩点以后用标号小的点来表示新点
    
       那我们发现每次后,剩下的0 到 X 联续的。
    
      我们可以每次拿掉一个 gcd 迭代。
    
      终止条件是 X与 T(迭代后的)互质。
    
     这样做的正确性比较显然吧。
    
      考试的时候simple的认为这是数论相关的。应该会带个u ,默默的减去 平方因子的贡献,非常神奇的是,过了大样例。然后华丽爆零
    #include<bits/stdc++.h>
    #define LL __int128
    using namespace std;
    LL gcd(LL x,LL y){return y?gcd(y,x%y):x;}
    LL sol(LL l,LL m,LL k){
        LL d=gcd(m,k);
        if (d==1) return l;
        if (l>k/d) return m*(k-l)/d+sol((k-m*(k-l))/d,m,k/d);
        return l;
    }
    int T;LL m,k;
    signed main () {
        scanf("%d",&T);
        while (T--) {
            scanf("%lld %lld",&m,&k);
            printf("%lld\n",sol(k-1,m,k)+1);
        } return 0;
    }
    
  • 1

信息

ID
2042
难度
3
分类
(无)
标签
递交数
31
已通过
17
通过率
55%
被复制
2
上传者