QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#921464#5. 在线 O(1) 逆元thomas0702#10 90ms32564kbC++14879b2025-02-28 22:45:512025-02-28 22:45:52

Judging History

This is the latest submission verdict.

  • [2025-02-28 22:45:52]
  • Judged
  • Verdict: 10
  • Time: 90ms
  • Memory: 32564kb
  • [2025-02-28 22:45:51]
  • Submitted

answer

#include<bits/stdc++.h>
#include"inv.h"
#define ll long long
using namespace std;
const int B=1<<10,B2=1<<21|1;
int P,pool[B2<<1],*iv=pool+B2,val[B2],aBu[B2];//[-2B^2,2B^2]
inline int mul(int x,int y){return (int)(1LL*x*y%P);}
void init(int __P){//P~1e9
	P=__P;
	int lim=P>>10;//P^{\frac{2}{3}}
	for(int u=1;u<=B;u++){//枚举u
		int x=0,uB=u<<10;
		for(int i=0;i<=lim;){
			if(x<=lim) val[i]=u;
			else if(x>=P-lim) val[i]=-u;
			else{
				int t=(P-lim-x-1)/uB;
				x+=t*uB,i+=t;
			}
			x+=uB,i++;
			if(x>=P) x-=P;
		}
	}
	for(int i=0;i<=lim;i++) aBu[i]=mul(i<<10,val[i]+P);
	iv[0]=0,iv[1]=1;
	for(int i=2;i<B2;i++) iv[i]=mul(P-P/i,iv[P%i]),iv[-i]=P-iv[i];
}
int inv(int x){//0<=x<P
//	assert(0<=x&&x<P);
	int a=x>>10,b=x&1023,u=val[a];
	return mul(u+P,iv[aBu[a]+b*u]);
}
//int main(){
//	const int P=998244353;
//	init(P);
//	return 0;
//}

Details


Pretests


Final Tests

Test #1:

score: 10
Accepted
time: 22ms
memory: 32300kb

Test #2:

score: 0
Wrong Answer
time: 79ms
memory: 32472kb

Test #3:

score: 0
Wrong Answer
time: 90ms
memory: 28252kb

Test #4:

score: 0
Wrong Answer
time: 88ms
memory: 32564kb

Test #5:

score: 0
Wrong Answer
time: 89ms
memory: 32540kb