QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#293465#5. 在线 O(1) 逆元iee70 ✓1328ms394424kbC++11358b2023-12-29 10:38:052023-12-29 10:38:07

Judging History

你现在查看的是测评时间为 2023-12-29 10:38:07 的历史记录

  • [2024-11-05 21:57:17]
  • 管理员手动重测本题所有提交记录
  • 测评结果:100
  • 用时:5721ms
  • 内存:394452kb
  • [2023-12-29 10:38:07]
  • 评测
  • 测评结果:70
  • 用时:1328ms
  • 内存:394424kb
  • [2023-12-29 10:38:05]
  • 提交

answer

#include "inv.h"

const int N = 1e8;
int mod;
int inv_list[N + 7];

void init(int p){
	mod = p;
	inv_list[0] = inv_list[1] = 1;
	for (register int i = 2; i <= N; i++){
		inv_list[i] = mod - 1ll * (mod / i) * inv_list[mod % i] % mod;
	}
}

int inv(int x){
	if (x <= N) return inv_list[x];
	return mod - 1ll * (mod / x) * inv(mod % x) % mod;
}

Details

Test #1:

score: 30
Accepted
time: 786ms
memory: 394424kb

Test #2:

score: 40
Accepted
time: 1328ms
memory: 394184kb

Test #3:

score: 0
Time Limit Exceeded