自动搬运

查看原文

来自洛谷，原作者为

	绿野 这帅得了懒癌，什么也没有留下是不可能的

搬运于2025-08-24 22:40:27，当前版本为作者最后更新于2022-10-27 16:33:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

优化的思路

如题 $0\leq x,k\leq 10^{18}$

然而 $3^{36} \approx 10^{18}$

因此若一直除 $3$，则 $n$ 顶多 $72$ 次运行到达个位。

但到达个位时，就可以找到一处“特殊的数字”来省去之后的运行。

特殊的数字

“一生二，二生三，三生万物。”

此数字就是 $1$。

经过调试很容易得到若剩余奇数次操作结果便为 $2$，不然为 $1$。

AC

#include<bits/stdc++.h>
using namespace std;
long long x,k;
int main(){
    cin>>x>>k;
    while(k--){
        x++;
        if(x%3==0)x/=3;
        if(x==1){//对1的特判切记莫放在x++前
            if(k%2==1){
                cout<<2;
                return 0;
            }
            else{
                cout<<1;
                return 0;
            }
        }
    }
    cout<<x;
    return 0;
}