{"problem":{"name":"[LSOT-1] 记忆崩塌","description":{"content":"**这是一道交互题。** 小 H 失忆了。 现在，小 H 过去的记忆化成了 $n$ 个记忆碎片。医生拥有 $n$ 种长度的取样条（长度为 $1\\dots n$）。记忆碎片会与长度为 $i$ 的取样条发生大小为 $\\gcd(n,i)$ 的情感共鸣。 医生有一个机器，可以测出长度为 $i$ 的取样条与小 H 产生的情感共鸣大小。现在你可以用这个机器测量一定的次数，医生希望你能告诉他若用完 $n$","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":5000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8450"},"statements":[{"statement_type":"Markdown","content":"**这是一道交互题。**\n\n小 H 失忆了。\n\n现在，小 H 过去的记忆化成了 $n$ 个记忆碎片。医生拥有 $n$ 种长度的取样条（长度为 $1\\dots n$）。记忆碎片会与长度为 $i$ 的取样条发生大小为 $\\gcd(n,i)$ 的情感共鸣。\n\n医生有一个机器，可以测出长度为 $i$ 的取样条与小 H 产生的情感共鸣大小。现在你可以用这个机器测量一定的次数，医生希望你能告诉他若用完 $n$ 种长度的取样条小 H 总共会发生多大的情感共鸣。\n\n### 交互格式\n你可以用以下格式来询问医生你想知道的东西：\n\n`TheSame? m`：下接 $m$ 行，每行两个数 $p_i,k_i$，医生会告诉你数小 H 的记忆碎片数量是否与 $\\displaystyle\\prod_{i=1}^mp_i^{k_i}$ 相等。`Yes` 代表相同或 `No` 代表不同。\n\n`GetGCD. m`：下接 $m$ 行，每行两个数 $p,k$ ，医生会告诉你$\\displaystyle\\prod_{i=1}^mp_i^{k_i}$  与小 H 的记忆碎片产生的情感共鸣大小。\n\n所有询问的 $p_i$ 为素数，$k_i$ 为正整数，不符合上述限制的交互不保证交互库会做出预期行为。\n\n***\n\n你可以用以下格式来告诉医生你知道的东西：\n\n`IFoundTheAnswer! m`：以此来告诉评测器我已经知道了小 H 总共产生的情感共鸣大小为 $m$，并评判是否正确。\n\n***\n\n你一共可以与医生交互 $1050$ 次。交互库的所有输出与你输出的答案均应对 $998244353$ 取模。\n\n***\n\n你需要从**标准输出**中输出，代表你询问的内容。\n\n每一次询问后都应当**清空缓冲区**，不然你会无缘无故 TLE。\n\n你可以使用如下语句来清空缓冲区：\n\n- 对于 C/C++：`fflush(stdout)`；\n- 对于 C++：`std::cout << std::flush`；\n- 对于 Java：`System.out.flush()`；\n- 对于 Python：`stdout.flush()`；\n- 对于 Pascal：`flush(output)`；\n- 对于其他语言，请自行查阅对应语言的帮助文档。\n\n特别的，对于 C++ 语言，在输出换行时如果你使用 `std::endl` 而不是 `'\\n'`，也可以自动刷新缓冲区。\n\n然后你需要从**标准输入**中输入，代表评测机返回的结果。\n\n## Input\n\n见「交互格式」。\n\n## Output\n\n见「交互格式」。\n\n[samples]\n\n## Background\n\n“铃铃铃”，上课铃打响。一阵眩晕，小 H 突然倒在地上。只是隐约间，感受到周围有人赶过来。\n\n“这是哪里？我不是在上课吗？”小 H 望向周围。\n\n“欢迎来到 OI 世界。我负责带你熟悉 OI 世界。”一个奇怪的人走到这里来。\n\n“OI 世界？”\n\n“对。这里没有文化课，你可以在这里尽情学习 OI。”那人解释道。\n\n紧接着，那人将小 H 带到了一个自称是心理学家的人面前。\n\n“你在干什么？”小 H 望着那个心理学家。他正准备把一个奇怪的东西戴到小 H 头上。\n\n“这个可以帮你恢复你在 whk 世界的记忆。”心理学家淡淡地说。\n\n仪器戴到头上后，小 H 大喊：“我什么都想起来了！”\n\n然而，真的什么都想起来了吗……\n\n从那个人带着小H前往OI世界观光开始，这一切，全都乱了……\n\n## Note\n\n【数据范围】\n\n**「本题采用捆绑测试」**\n\n- $\\texttt{Subtask 1(10 pts)：}1 \\le\\ n\\le 500$；\n- $\\texttt{Subtask 2(25 pts)：}1 \\le\\ n\\le 10^6$；\n- $\\texttt{Subtask 3(25 pts)：}$保证 $n$ 的唯一分解形式仅有前 $100$ 个质数；\n- $\\texttt{Subtask 4(40 pts)：}$无特殊限制。\n\n对于 $100\\%$ 的数据，满足 $n$ 的唯一分解形式质数数量不超过 $1000$，且质因子最大不超过 $7919$（注：$7919$ 为第 $1000$ 个质数），且质数的次数不超过 $10000$。\n\n【其他提示】\n\n因为交互库的效率较低，所以附件中给出交互库的代码。如果你想利用下面的交互库代码进行调试，你可以在官方的 [SPJ 说明](https://www.luogu.com.cn/blog/luogu/special-judge) 中下载 ```testlib.h``` 头文件后将两个程序的输出输入到另一个程序中。当然，你也可以模拟交互库的计算来手动输入到你的程序中。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8450","tags":["动态规划 DP","原根","数论","交互题","Special Judge","O2优化"],"sample_group":[["1\nNo\n2\nYes","GetGCD. 0\nTheSame?  0\nGetGCD. 1\n2 1\nTheSame? 1\n2 1\nIFoundTheAnswer! 3"]],"created_at":"2026-03-03 11:09:25"}}