P5285

这个代码时间复杂度看起来完全正确，但是 tle？

注意：代码还没写完

#include<bits/stdc++.h>
using namespace std;
long long m,b,mod,t,x,y;
bool flag=0;
string id;
long long p[]={0,2,3,5,13,17,31,37};
inline int read(){
	long long ret=0,f=1;char ch;
	while((ch=getchar())<'0'||ch>'9')if(ch=='-')f=-1;
	while(ch>='0'&&ch<='9'){
		(ret=(ret<<1)+(ret<<3)+(ch^48)),ch=getchar();
		while(ret>=mod){
			flag=1;
			ret%=mod;
		}
	}
	return ret%mod*f;
}
long long gsc(long long n,long long k,long long md){
	long long p=0,q=n%md;
	while(k){
		if(k&1)p=(p+q)%md;
		q=(q<<1)%md;
		k>>=1;
	}
	return p;
}
long long qpow(long long n,long long k,long long md){
	long long p=1,q=n%md;
	while(k){
		if(k&1)p=gsc(p,q,md)%md;
		q=gsc(q,q,md)%md;
		k>>=1;
	} 
	return p;
}
bool Miller_Rabin(long long n,long long a){
	long long vp=n-1,r=0,pan;
	while(!(vp&1))r++,vp>>=1;
	pan=qpow(a,vp,n);
	if(pan==1)return 1;
	for(int i=0;i<r;i++){
		if(pan==n-1)return 1;
		pan=gsc(pan,pan,n);
	}
	return 0;
}
bool isp(long long n){
	if(n<2)return 0;
	for(int i=1;i<=7;i++){
		if(n==p[i])return 1;
		if(n%p[i]==0)return 0;
		if(!Miller_Rabin(n,p[i]))return 0;
	}
	return 1;
}
int main(){
	cin>>id;
	if(id=="1_998244353"){
		m=998244353;
		mod=998244352;
		cin>>t;
		while(t-->0){
			flag=0;
			b=read();
			if(flag==1)printf("%lld\n",qpow(19,b+mod,m));
			else printf("%lld\n",qpow(19,b,m));
		}
	}else if(id=="1?"){
		m=1145141;
		mod=1145140;
		cin>>t;
		while(t-->0){
			flag=0;
			b=read();
			if(flag==1)printf("%lld\n",qpow(19,b+mod,m));
			else printf("%lld\n",qpow(19,b,m));
		}
	}else if(id=="1?+"){
		m=5211600617818708273ll;
		mod=5211600617818708272ll;
		cin>>t;
		while(t-->0){
			flag=0;
			b=read();
			if(flag==1)printf("%lld\n",qpow(19,b+mod,m));
			else printf("%lld\n",qpow(19,b,m));
		}
	}else if(id=="2p"){
		cin>>t;
		while(t-->0){
			scanf("%lld%lld",&x,&y);
			cerr<<"ppp\n";
			for(;x<=y;x++){
				if(isp(x))putchar('p');
				else putchar('.');
			}
		}
		puts("");
	}
}