QOJ.ac

QOJ

Time Limit: 6 s Memory Limit: 512 MB Total points: 100 Interactive
[+55]

# 5. 在线 O(1) 逆元

Statistics

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

题目描述

n 次询问,每次询问一个 x,求出它取模 p 意义下的逆元 x1

实现细节

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

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

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

子任务

对于所有数据,1n108,p=998244353

  • Subtask 1(10 Points): n105
  • Subtask 2(20 Points): n107
  • Subtask 3(30 Points): n5×107
  • Subtask 4(20 Points): n8×107
  • Subtask 5(20 Points): No additional constraints.