题解 P8588 【『JROI-8』雷雨天特别行动科】

非常简单的一道题目,但是不要想得太简单(好歹是橙题不是红题(狗头

问题出在题目的数据范围上——发现一道 $10^{18}$ 的题目,不仅要想到 long long ,还要注意到以 $\Theta{(K)}$ 的复杂度直接模拟一定是没法通过的。

那么怎么办呢?仔细阅读题目发现,$x$ 始终在 $3$ 的余数中产生循环,因此打个表可以发现规律:

19 20 21->7 8 9->3 4 5 6->2 
3->1 2 3->1 2 3->1 2 3->1 ...

既然如此,我们可以发现:如果 $x$ 比 $2$ 大前就结束循环,则可以直接输出计算的值,且因为 $\log_{3}{10^{18}}\approx38$,在 $38 \times 3$ 左右次循环中即可实现,复杂度可以通过;如果 $x$ 最后等于 $1$ 或 $2$,则说明它已经进入了 1->2 的循环之中,只需要通过 $k$ 的奇偶性分类讨论即可。

以下是代码。

#include <iostream>
using namespace std;
long long x, k;
int main() {
cin >> x >> k;
while (k--) {
x ++;
if (x % 3 == 0) x /= 3;
if (x == 1) break; //在x=2时没有break,是为了减少后续处理的难度
}
if (k <= 0) cout << x << endl;
else if (k % 2 == 0) cout << 1 << endl;
else if (k % 2 == 1) cout << 2 << endl;
return 0;
}

完结撒花~