{"problem":{"name":"「SvR-1」Hack Function!","description":{"content":"此时的 J-PSC 终于改成了 CF 赛制，小 C 迅速地 AK 了 Day 1，他发现 T2 function 比较好 Hack，题目的人话翻译如下： > 对于一个数 $A$，定义函数 $f(A)$ 如下： >  > 1. 先把 $A$ 变成 $k$ 进制数 $B$。 > 2. 将 $A$ 替换为 $B$ 各位之和。 > 3. 返回执行第 1 步，直到 $B$ 是一位数为止。 > 4. 记 $","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8412"},"statements":[{"statement_type":"Markdown","content":"此时的 J-PSC 终于改成了 CF 赛制，小 C 迅速地 AK 了 Day 1，他发现 T2 function 比较好 Hack，题目的人话翻译如下：\n\n> 对于一个数 $A$，定义函数 $f(A)$ 如下：\n> \n> 1. 先把 $A$ 变成 $k$ 进制数 $B$。\n> 2. 将 $A$ 替换为 $B$ 各位之和。\n> 3. 返回执行第 1 步，直到 $B$ 是一位数为止。\n> 4. 记 $x$ 表示 $A$ 此时的值（十进制）。\n> 此时 $f(A) = x$，$f(A)$ 称作 $A$ 关于 $k$ 的**位和函数**。\n>\n> 给定 $k, l, r, p$，求出 $\\sum_{i = l}^r f(i^i) \\bmod p$ 的值。\n>\n> **特别地，当 $\\sum_{i = l}^r f(i^i) = p$ 时，输出 $\\texttt{perfect}$。**\n\n小 C 迅速秒了该题，当他翻看别人的代码时，发现他们用的全是暴力枚举。（因为机子跑得飞快）\n\n好不容易看到一个人，他的代码里竟然没有一个  $\\texttt{perfect}$！但由于数据过弱，竟然让他 pp 了。\n\n小 C 突然脑子一热，忘记了怎么构造 Hack 数据，所以他通过 Luogu 6.0 求助于你。\n\n小 C 会告诉你 $k, p$ 的值，你需要构造一组 $l, r$，**使答案输出为 $\\texttt{perfect}$**。\n\n**若无法构造，输出两个 $\\texttt{-1}$。**\n\n## Input\n\n**本题有多组数据。**\n\n第一行一个整数 $T$，表示数据组数。\n\n接下来 $T$ 行，每行两个整数 $k,p$，含义如题所述。\n\n## Output\n\n共 $T$ 行，对于每组数据，输出你构造的 $l,r$ 的值。\n\n若有多组解，输出任意一组。\n\n[samples]\n\n## Background\n\n**Problem Number:** $\\textit{63}$\n\n小 C 坐在 J-PSC2077 的赛场（题目可于下方「**题目附件**」处下载）上，他早已年逾七旬，但作为 Z 队选手还是成功参赛。\n\n## Note\n\n#### 样例 1 说明\n\n- 对于数据 $1$，在 $k = 10$ 下，有 $f(2^2) = f(4) = 4$，$f(3^3) = f(27) = 9$，显然 $l = 2, r = 3$ 时原题应该输出 $\\texttt{perfect}$。\n- 对于数据 $2$，在 $k = 10$ 下，发现不可能满足要求。\n- 对于数据 $3$，在 $k = 2$ 下，显然有 $f(1^1) = 1$，但该样例仅用于理解，根据数据规模与约定，我们保证 $k \\geq 10$。\n\n#### 数据规模与约定\n\n$$\n\\newcommand{\\arraystretch}{1.5}\n\\begin{array}{c|c|c|c}\\hline\\hline\n\\textbf{Subtask} & \\textbf{说明} & \\textbf{时限} & \\textbf{分值} \\\\\\hline\n\\textsf{1} & \\text{无解} & 1\\text{ s} & 3 \\\\\\hline\n\\textsf{2} & \\text{有解且\\textbf{\\textsf{存在}}一组解使 }1\\le l\\le r\\le 10^5 & 1\\text{ s} & 16 \\\\\\hline\n\\textsf{3} & 1\\le p\\le 10^7 & 1\\text{ s} & 34 \\\\\\hline\n\\textsf{4} & \\text{无特殊限制} & 1.5\\text{ s} & 47 \\\\\\hline\\hline\n\\end{array}\n$$\n\n对于 $100\\%$ 的数据，$10 \\leq k \\leq 10^3$，$1 \\leq p \\leq 10^8$，$1 \\leq T \\leq 10$。\n\n保证时限在 std 用时的 $4$ 倍以上。\n\n#### 评测说明\n\n**本题开启 Special Judge 和捆绑测试。**\n\n你需要保证 $l = r = -1$ 或 $1 \\leq l \\leq r \\leq 10^{18}$ 且 $r - l \\leq 10^{15}$，否则 SPJ 会将你的答案判为 $0$ 分。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8412","tags":["2022","洛谷原创","Special Judge","O2优化","构造","洛谷月赛"],"sample_group":[["3\n10 13\n10 3\n2 1","2 3\n-1 -1\n1 1"]],"created_at":"2026-03-03 11:09:25"}}