Codeforces Round #194 Div1A Secrets

問題

ある国ではお金は１マルク硬貨、３マルク硬貨、９マルク硬貨、２７マルク硬貨、・・・（以下無限）
があります。
Nマルクの支払いをするときに、丁度になるようには払えなくて、お釣りをもらわないとならないことがあります（たとえば３マルク硬貨１枚しか持っていないと、２マルク丁度は払えません）。
このとき、渡す硬貨の枚数が一番少なくなるように渡します。
７マルク払えと言われて３マルク３枚と９マルク１枚を持っていたら、後者１枚で支払うということになります。

こういうふうになる硬貨の組み合わせは（Nに対して）たくさんありますが、
払う硬貨の枚数は最大で何枚になるでしょうか？

制約
1<=n<=10^17

解法

少し思考実験をすると、
NをMで割り切れる場合、Mマルク（以下の価値の）硬貨は最小枚数支払いに絡んでこないということがわかります。
なぜなら、それが最小枚数支払いに絡んでくる場合、お釣りが出ないような払い方が可能だからです。

例えば支払額が15マルクだった場合、３マルク硬貨の所持数は丁度支払えない仮定から高々４枚ですが、
１．27マルク以上の硬貨を持っている場合。
最小支払い枚数はそれ１枚になります。
２．9マルク硬貨を０か１つ持っている場合。
NがMで割り切れるので、（N-M*3）もMで割り切れます。なのでお釣りが出ないような支払い方がそもそもできちゃいます。
３．9マルク硬貨を2枚以上持っている場合。
最小支払い枚数は9マルク硬貨2枚となります。

というわけで、「Nを割り切れない最小のMマルク硬貨を（N/M+1）枚使って支払う」のが最大の支払い最小枚数となります。

プログラム

というわけでプログラム自体は極めて単純になります。

#include<iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include<string>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<sstream>
#include<algorithm>
#include<map>
#include<complex>
using namespace std;


#define li			long long int
#define rep(i,to)	for(int i=0;i<((int)(to));i++)
#define repp(i,start,to)	for(int i=(int)(start);i<((int)(to));i++)
#define pb			push_back
#define sz(v)		((li)(v).size())
#define bgn(v)		((v).begin())
#define eend(v)		((v).end())
#define allof(v)	(v).begin(), (v).end()
#define dodp(v,n)		memset(v,(li)n,sizeof(v))
#define bit(n)		(1ll<<(li)(n))
#define mp(a,b)		make_pair(a,b)
#define rin	rep(i,n)
#define EPS 1e-10
#define ETOL 1e-8
#define MOD 1000000007
#define p2(a,b)		cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)		cout<<a<<"\t"<<b<<"\t"<<c<<endl


int main(){
	li n;
	cin>>n;
	
	li warikire=1;
	while(n%warikire==0)warikire*=3;
	cout<<n/warikire+1<<endl;
	
	return 0;
}