CF333A Secrets 题解

BYWYR · 2022-08-08 12:41:08 · 题解

\texttt{Solution}

想要顾客付的硬币数量最少，我们要最大化每个硬币的价值，也就是说他付的钱一定为 3^{x_{max}} 元。

且 n \text{mod} 3 \neq 0，那么他付的最少硬币数量就为 \left\lceil\dfrac{n}{3^{x_{max}}}\right\rceil 个。

注意：此处变量要开 \text{long long}，因为题目中说 1 \leq n \leq 10^{17}。

\texttt{Code}

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,coin=1;//不开 long long 见祖宗
//最初硬币价值应为1，否则初始为0乘起来永远是0
int main(){
    cin>>n;
    while(n%coin==0){
        coin*=3;//最大化每个硬币的价值
    }
    cout<<ceil(n/coin);//硬币的数量
    return 0;
}