#P12478. [2025年福建省队集训]Soyo 的秘密

    ID: 11641 交互题 2000ms 512MiB 尝试: 13 已通过: 1 难度: 10 上传者: 标签>组合数学CF3000构造数学分治模拟状压DP

[2025年福建省队集训]Soyo 的秘密

[2025年福建省队集训] Soyo 的秘密

题目描述

Soyo 事先选定一个隐藏整数 X∈[1,N]X\in[1,N]。你每次可以询问一个非负整数 Y≤CY\le C,她会回答 X+YX+Y 的正因数个数,XX 不会随询问改变。你需要在总共不超过 QQ 次询问内,依次求出 TT 个隐藏整数。

交互接口

实现主函数并包含 divisors.h。只能通过以下六个函数交互,不能在程序中自行读入或输出其他内容。

int GetT();
long long GetN();
int GetQ();
long long GetC();
long long Ask(long long y);
void Answer(long long x);

前四个函数返回本测试点固定的 T,N,Q,CT,N,Q,C,重复调用时不变。Ask(y) 返回当前隐藏整数加 yy 的正因数个数。QQ 是求出全部 TT 个整数的总询问上限,不会在 Answer 后重置。

Answer(x) 报告当前隐藏整数。回答正确后开始下一个整数;回答最后一个整数后应立即正常退出。询问越界、超过总次数、答案错误、少答或额外输出均不能通过。

本地测试

下列输入是交互器的输入,选手程序不能直接读取隐藏整数。第一行 T,N,Q,CT,N,Q,C,接下来 TT 行依次为隐藏的 XX。交互器在全部回答正确且不超限时判定通过,否则给出原因。

2 1000000 10000 100000000000000000
1000
1

一次可能的过程:GetT() 返回2,GetQ() 返回10000;对第一个数,Ask(1) 返回8(1001=7×11×131001=7\times11\times13),Ask(3) 返回4(1003=17×591003=17\times59),然后 Answer(1000)。对第二个数,GetT() 仍返回2,Ask(0) 返回1,Ask(99) 返回9(100=22×52100=2^2\times5^2),最后 Answer(1)。

下载 交互器源码、testlib.h、双进程测试脚本 和 样例数据。将它们与自己的程序放在同一目录,编译并运行:

g++ -std=c++17 -O2 your.cpp -o participant
g++ -std=c++17 -O2 interactor.cpp -o interactor
python local_runner.py sample.in --program ./participant --interactor ./interactor

Windows 下可把程序名改为 participant.exe 和 interactor.exe。平台使用独立进程保管隐藏整数,给选手的头文件只负责调用协议,不包含隐藏数据或判定答案的代码。

数据范围

原题共25个等分测试点,每点4分,总分100。下表列出原测试点参数:

测试点 T N Q C
1–3 50 10510^5 5×1045\times10^4 101210^{12}
4–6 10610^6 5×1035\times10^3
7–12 10 10910^9 5×1045\times10^4
13–16 101410^{14} 5×1035\times10^3 101710^{17}
17–18 2×1032\times10^3
19–20 1300
21–22 950
23 820
24 750
25 720

一般范围为 10≤T≤5010\le T\le50、1≤N≤10141\le N\le10^{14}、72T≤Q72T\le Q、1≤C≤10171\le C\le10^{17};上面的原样例 T=2T=2 单独展示接口使用。原题说明下发grader与实际grader不同,grader对合法调用的耗时不超过0.2秒、空间不超过128MB。

原始题面图

原题第1部分

原题第2部分

原题第3部分

原题第4部分

原题第5部分

原题第6部分