P8588 『JROI-8』雷雨天特别行动科

· · 题解

优化的思路

如题

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;
}