QOJ.ac

QOJ

Time Limit: 6 s Memory Limit: 512 MB Total points: 100 Interactive

# 5. 在线 O(1) 逆元

Statistics

这是一道交互题,本题仅支持 C++ 语言。

题目描述

$n$ 次询问,每次询问一个 $x$,求出它取模 $p$ 意义下的逆元 $x^{-1}$。

实现细节

你不需要,也不应该实现 main 函数。你只需要包含头文件 inv.h,并实现以下接口:

void init(int p)
  • 该函数接收一个参数 $p$,表示取模的模数。
  • 该函数会在每个测试点调用 query 前被调用恰好一次。
  • 在评测时,保证 $p = 998\,244\,353$。
int inv(int x)
  • 该函数接受一个参数 $x(0 \leq x < p)$。
  • 该函数需要返回 $x$ 在模 $p$ 意义下的逆元。

交互库将调用 inv 恰好 $n$ 次。

子任务

对于所有数据,$1 \leq n \leq 10^8, p=998244353$

  • Subtask 1(30 Points): $n \leq 10^5$
  • Subtask 2(40 Points): $n \leq 10^7$
  • Subtask 3(30 Points): No additional constraints.