P8588题解

Steroids · 2022-10-23 13:10:30 · 题解

在csp前写点题解刷rp

P8588 题解

一道好玩的小思维题。

看到题目第一想法是模拟，然后看到了数据范围/jk。

思路分析

题目里最大是 10^ {18} ，开 long long 就可以。

但是 k 最大是 10^{18}，所以要找规律。

我们会发现，在经过一定操作后，答案固定在一到二之间。

题目中是加一除三的操作，所以我们可以算一下最大是三的几次幂（这里是四十就够了）。

在输入后特判一下 k 是否大于 120，大于就可以直接预处理，最后根据 k 的奇偶性判断是 1 还是 2 就行了。

至于时间复杂度是 O(1)，本来就只有120的预处理，最后的%2也是 O(1)。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<utility>
#include<map>
#include<string>
#include<cstring>
#define int long long
using namespace std;
signed main(){
    int a,b;
    cin>>a>>b;
    if(b<=120){//这里选用120是因为到三的倍数最多要三次。
        for(int i=1;i<=b;i++){
            a+=1;
            if(a%3==0)a/=3;
            }
        cout<<a;
        return 0;
    }
    for(int i=1;i<=120;i++){
        a+=1;
        if(a%3==0)a/=3;
    }
    b-=120;
    b%=2;
    for(int i=1;i<=b;i++){
        a+=1;
        if(a%3==0)a/=3;
    }
    cout<<a;
    return 0;
}