C++ 解法, 执行用时: 236ms, 内存消耗: 20596K, 提交时间: 2021-08-28 15:49:00

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll,ll>mp;
ll t, n;
ll solve(ll n){
	if(n < 6) return n;
	if(mp[n]) return mp[n];
	ll i = 1, j = 1;
	while(i*6 <=n) i*=6;
	while(j*9 <=n) j*=9;
	return mp[n] = min(solve(n-i), solve(n-j))+1;
}

int main(void){
	cin >>t;
	while(t--){
		cin >> n;
		cout << solve(n) << endl;
	}
	return 0;
}

Python3 解法, 执行用时: 908ms, 内存消耗: 27500K, 提交时间: 2021-08-20 22:46:48

from math import*

d = dict()
def f(n):
	if n<=5: return n
	if n in d: return d[n]

	val1 = 6**int(log(n)/log(6))
	val2 = 9**int(log(n)/log(9))
	d[n] = int(1e15)
	if(val1>0):
		d[n] = min(d[n], f(n-val1)+1)
	if(val2>0):
		d[n] = min(d[n], f(n-val2)+1)
	return d[n]
t = int(input())
while t:
    t -= 1
    print(f(int(input())))