这是一道交互题,本题仅支持 C++ 语言。
题目描述
n 次询问,每次询问一个 x,求出它取模 p 意义下的逆元 x−1。
实现细节
你不需要,也不应该实现 main 函数。你只需要包含头文件 inv.h
,并实现以下接口:
void init(int p)
- 该函数接收一个参数 p,表示取模的模数。
- 该函数会在每个测试点调用
query
前被调用恰好一次。 - 在评测时,保证 p=998244353。
int inv(int x)
- 该函数接受一个参数 x(0≤x<p)。
- 该函数需要返回 x 在模 p 意义下的逆元。
交互库将调用 inv
恰好 n 次。
子任务
对于所有数据,1≤n≤108,p=998244353
- Subtask 1(10 Points): n≤105
- Subtask 2(20 Points): n≤107
- Subtask 3(30 Points): n≤5×107
- Subtask 4(20 Points): n≤8×107
- Subtask 5(20 Points): No additional constraints.