P8308 〈 TREEのOI 2022 Spring 〉Counting By Ternary
题目背景
黑土地上，一棵小苗破土而出。
几个月里，它吮吸着甘甜的雨露，享受着温暖的阳光，愈发翠绿了起来。
它越长越高，越长越壮，似乎要突破云霄。
它长成了一棵大树，渴望着去天空中，看一看这美丽的世界。
题目描述
**请留意本题并不寻常的时空限制。**
给定一个数 $x$，用如下规则建立一棵有根树：
- 根节点为 $\lang0,x\rang$。
- 对于一个节点 $\lang i,j\rang$，若 $j < 3$，则它是叶子节点，否则它的子节点为对于任意 $1 \le k$ 且 $j$ 的位数 $\ge k$， $\lang j_k, k\rang$，其中 $j_k$ 为它三进制表示从左向右的第 $k$ 位。
求这棵树的叶子节点的数目。
输入格式
无
输出格式
无
说明/提示
**本题采用 SubTask 捆绑测试。**
| SubTask 编号 | 分值 | 特殊性质 |
| :-----------: | :-----------: | :-----------: |
| $0$ | $10$ | $p\le 3^{15}$，$q=1$ |
| $1$ | $10$ | $p\le 3^{35}$，$q=1$ |
| $2$ | $20$ | $p=3$，$q\le 3^{15}$ |
| $3$ | $60$ | $p=3$，$q\le 3^{35}$ |
对于 $100\%$ 的数据，$p^q \le 3^{3^{35}}$（$10^{10^9} \lt 3^{3^{35} } \lt 10^{2.5 \times 10^9}$），保证 $p = 3^l(l\in \mathbb N^+)$。