〈 TREEのOI 2022 Spring 〉Counting By Ternary

Luogu
IDLGP8308
Time300ms
Memory64MB
DifficultyP4
数学递推O2优化前缀和分块
**请留意本题并不寻常的时空限制。** 给定一个数 $x$,用如下规则建立一棵有根树: - 根节点为 $\lang0,x\rang$。 - 对于一个节点 $\lang i,j\rang$,若 $j < 3$,则它是叶子节点,否则它的子节点为对于任意 $1 \le k$ 且 $j$ 的位数 $\ge k$, $\lang j_k, k\rang$,其中 $j_k$ 为它三进制表示从左向右的第 $k$ 位。 求这棵树的叶子节点的数目。 ## Input 一行两个整数 $p, q$,表示 $x = p^q$。 ## Output 一行一个整数,即为所求。 题目保证答案在 $\tt int64$ 范围内。 [samples] ## Background 黑土地上,一棵小苗破土而出。 几个月里,它吮吸着甘甜的雨露,享受着温暖的阳光,愈发翠绿了起来。 ![](https://cdn.pixabay.com/photo/2019/03/05/12/52/plant-4036131_960_720.jpg) 它越长越高,越长越壮,似乎要突破云霄。 它长成了一棵大树,渴望着去天空中,看一看这美丽的世界。 ![](https://cdn.pixabay.com/photo/2015/02/24/15/41/wolf-647528_960_720.jpg) ## Note **本题采用 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^+)$。
Samples
Input #1
9 1
Output #1
4
Input #2
27 1
Output #2
6
API Response (JSON)
{
  "problem": {
    "name": "〈 TREEのOI 2022 Spring 〉Counting By Ternary",
    "description": {
      "content": "**请留意本题并不寻常的时空限制。** 给定一个数 $x$,用如下规则建立一棵有根树: - 根节点为 $\\lang0,x\\rang$。   - 对于一个节点 $\\lang i,j\\rang$,若 $j < 3$,则它是叶子节点,否则它的子节点为对于任意 $1 \\le k$ 且 $j$ 的位数 $\\ge k$, $\\lang j_k, k\\rang$,其中 $j_k$ 为它三进制表示从左向右的",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 300,
      "memory_limit": 65536
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8308"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "**请留意本题并不寻常的时空限制。**\n\n给定一个数 $x$,用如下规则建立一棵有根树:\n\n- 根节点为 $\\lang0,x\\rang$。  \n\n- 对于一个节点 $\\lang i,j\\rang$,若 $j < 3$,则它是叶子节点,否则它的子节点为对于任意 $1 \\le k$ 且 $j$ 的位数 $\\ge k$, $\\lang j_k, k\\rang$,其中 $j_k$ 为它三进制表示从左向右的...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments