CF1982B Collatz Conjecture

原题链接：B. Collatz Conjecture

Tag：暴力模拟

题目描述

给定一个 \(x\)、一个 \(y\) 和一个 \(k\)。 \(k\) 代表执行了 \(k\) 次操作，每次操作依次执行两步：

\(x\) 增加 \(1\)。
当数字 \(x\) 能被 \(y\) 整除时，除以 \(y\)。

问 \(k\) 次操作都执行完之后 \(x\) 是多少。

分析

首先可以想到如果某个时刻 \(x\) 变成 \(1\) 了，那么这个时候这个操作就出现了一个长度为 \(y - 1\) 的循环节，这个时候稍微动用一下你大脑的智慧算一下就好了。

当 \(x \neq 1\) 并且 \(k \neq 0\) 的时候我们进行暴力模拟，不满足条件的时候，如果 \(k = 0\)，代表操作都做完了，直接输出 \(x\) 就是对的。

除此之外就是 \(x = 1\) 的情况了，在这种情况下已经说了会出现一个长度为 \(y - 1\) 的循环节，所以我们直接模一下就可以了

代码实现

void NeverSayNever() {
    int x, y, k;
    cin >> x >> y >> k;
    while (x != 1 && k != 0) {
        int z = x % y;
        int tmp = min(y - z, k);
        if (tmp == 0) {
            tmp = min(y, k);
        }
        x += tmp;
        k -= tmp;
        while (x % y == 0) {
            x /= y;
        }
    }
    if (k == 0) {
        cout << x << endl;
    } else {
        cout << x + k % (y - 1) << endl;
    }
}

额外思考

本体赛时单防了我四十分钟，因为我拿不准时间复杂度没敢写，最后实在受不了弄了个看起来就要TLE的，结果跑的飞快，嘻嘻。

日志

本页面创建于 2024/6/26 02:06