问题描述

Boss Niu（Niu Niu）是当地的大亨。他有无限的钞票，但他的钞票有一个奇怪的面值：

NIU boss钞票的面值是6i6i或9i9i，其中（i∈[-∞，∞]）（i∈[−∞，∞]），ii是整数。

老板Niu买了一架私人飞机，并以xx的价格出售了它。老板NIU希望在不改变的情况下尽可能少的钞票付款。请帮助Boss Niu至少计算需要多少钞票。

输入描述：

输入包含TT组测试用例，第一行是整数TT

接下来，每条TT线都有一个整数xx

输出描述：

输出TT行，第ii行为第ii组测试用例的答案。

示例1

进入

复制

4 6 9 998244353 1000000007

输出

复制

1 1 17 17

评论：

1≤T≤40,1≤X≤1e121≤T≤40,1≤X≤1e12

#include #include #include #include

using namespace std; typedef long long ll; map m; int solve(ll x){ if(m[x]) return m[x]; if(x==0) return 0; ll r6=1,r9=1; while(r6*6<=x) r6*=6; while(r9*9<=x) r9*=9; return m[x]=min(solve(x-r6),solve(x-r9))+1; } int main(){ int t; ll p=1; while(p<=1e12){ m[p]=1; p*=6; } while(p<=1e12){ m[p]=1; p*=9; } cin>>t; while(t--){ ll x; cin>>x; cout<<