QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#241461#5. 在线 O(1) 逆元mfeitveer80 5546ms238284kbC++14386b2023-11-06 08:02:252024-11-05 21:54:28

Judging History

This is the latest submission verdict.

  • [2024-11-05 21:54:28]
  • 管理员手动重测本题所有提交记录
  • Verdict: 80
  • Time: 5546ms
  • Memory: 238284kb
  • [2023-11-06 08:02:27]
  • Judged
  • Verdict: 70
  • Time: 1096ms
  • Memory: 237892kb
  • [2023-11-06 08:02:25]
  • Submitted

answer

#include "inv.h"

const int N = 30000010;
const int mod = 998244353;

typedef long long ll;

ll Inv[N];

ll ask(ll x)
{
    if(x <= 30000000) return Inv[x];
    return (mod - mod / x) * ask(mod % x) % mod;
}

void init(int p)
{
	Inv[1] = 1;
	for(int i = 2;i <= 30000000;i++)
		Inv[i] = (mod - mod / i) * Inv[mod % i] % mod;
}

int inv(int x)
{
	return ask(x);
}

Details


Pretests


Final Tests

Test #1:

score: 10
Accepted
time: 353ms
memory: 238136kb

Test #2:

score: 20
Accepted
time: 981ms
memory: 238284kb

Test #3:

score: 30
Accepted
time: 3579ms
memory: 238280kb

Test #4:

score: 20
Accepted
time: 5546ms
memory: 238276kb

Test #5:

score: 0
Time Limit Exceeded