{"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$ 为它三进制表示从左向右的第 $k$ 位。  \n\n求这棵树的叶子节点的数目。\n\n## Input\n\n一行两个整数 $p, q$，表示 $x = p^q$。\n\n## Output\n\n一行一个整数，即为所求。  \n\n题目保证答案在 $\\tt int64$ 范围内。\n\n[samples]\n\n## Background\n\n黑土地上，一棵小苗破土而出。\n\n几个月里，它吮吸着甘甜的雨露，享受着温暖的阳光，愈发翠绿了起来。\n\n![](https://cdn.pixabay.com/photo/2019/03/05/12/52/plant-4036131_960_720.jpg)\n\n它越长越高，越长越壮，似乎要突破云霄。\n\n它长成了一棵大树，渴望着去天空中，看一看这美丽的世界。\n\n![](https://cdn.pixabay.com/photo/2015/02/24/15/41/wolf-647528_960_720.jpg)\n\n## Note\n\n**本题采用 SubTask 捆绑测试。**\n\n| SubTask 编号 | 分值 | 特殊性质 |\n| :-----------: | :-----------: | :-----------: |\n| $0$ | $10$ | $p\\le 3^{15}$，$q=1$ |\n| $1$ | $10$ | $p\\le 3^{35}$，$q=1$ |\n| $2$ | $20$ | $p=3$，$q\\le 3^{15}$ |\n| $3$ | $60$ | $p=3$，$q\\le 3^{35}$ |\n\n对于 $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^+)$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8308","tags":["数学","递推","O2优化","前缀和","分块"],"sample_group":[["9 1","4"],["27 1","6"]],"created_at":"2026-03-03 11:09:25"}}