题解

#include <bits/stdc++.h>
using namespace std;
#define RI register int
typedef unsigned long long uLL;
typedef long long LL;
char typ[50];
namespace work1
{
	uLL mul(uLL x,uLL y,uLL mod)
	{
		if(x<1e9 && y<1e9) return x*y%mod;
		uLL re=0;
		for(; y; y>>=1,x=(x+x)%mod) if(y&1) re=(re+x)%mod;
		return re;
	}
	void work(uLL mod)
	{
		char S[50];
		int len,T;
		cin>>T;
		while(T--)
		{
			scanf("%s",S+1),len=strlen(S+1);
			uLL y=0,re=1,x=19;
			for(RI i=1; i<=len;
			        ++i) y=(mul(10uLL,y,mod-1)+(uLL)(S[i]-'0'))%(mod-1);
			for(; y; y>>=1,x=mul(x,x,mod)) if(y & 1) re=mul(re,x,mod);
			printf("%llu\n",re);
		}
	}
};
namespace work2
{
	const int mod=998244353;
	int a[100950],T;
	void work()
	{
		a[0]=1;
		for(RI i=1; i<=100944; ++i) a[i]=a[i-1]*19%mod;
		cin>>T;
		while(T--)
		{
			uLL x;
			scanf("%llu",&x);
			if(x<=100944LL) cout<<a[x]<<endl;
			else cout<<a[(x-55245)%45699+55245]<<endl;
		}
	}
};
LL qmul(LL x,LL y,LL p)
{
	if(x<=2e9 && y<=2e9) return 1LL*x*y%p;
	return (x*y-(LL)((long double)x/p*y+0.5)*p+p)%p;
}
LL qpow(LL x,LL y,LL p)
{
	LL re=1;
	for(; y; y>>=1,x=qmul(x,x,p)) if(y&1) re=qmul(re,x,p);
	return re;
}
int Miller_Rabin(LL n,int lim_kas)
{
	if(n==2 || n==3 || n==5 || n==7 || n==11 || n==13) return 1;
	if(n%2==0 || n%3==0 || n%5==0 || n%7==0 || n%9==0 || n%11==0 || n%13==0) return 0;
	LL k=n-1,t=0;
	while(!(k&1))
	{
		t++;
		k>>=1;
	}
	for(RI kas=1; kas<=lim_kas; ++kas)
	{
		LL x=qpow(rand()%(n-2)+2,k,n),y;
		for(LL i=1; i<=t; ++i)
		{
			y=x;
			x=qmul(x,x,n);
			if(x==1 && y!=1 && y!=n-1) return 0;
		}
		if(x!=1) return 0;
	}
	return 1;
}
namespace work3
{
	void work()
	{
		LL l,r;
		int T;
		cin>>T;
		cin>>l>>r,puts("pp.p.p...");
		cin>>l>>r,puts("p.p...");
		cin>>l>>r,puts("pp.p.p...p.p..");
		cin>>l>>r;
		for(LL i=l; i<=r; ++i) putchar(Miller_Rabin(i,10)?'p':'.');
		puts("");
	}
};
namespace work4
{
	int tot,pri[1000005],is[1000005],mu[1000005];
	LL x[1000005];
	void work()
	{
		LL l,r;
		int T;
		cin>>T;
		cin>>l>>r,puts("--0-+-00+");
		cin>>l>>r,puts("-+-00+");
		cin>>l>>r,puts("--0-+-00+-0-++");
		cin>>l>>r;
		for(RI i=2; i<=1000000; ++i)
		{
			if(!is[i]) pri[++tot]=i;
			for(RI j=1; j<=tot && pri[j]*i<=1000000; ++j)
			{
				is[pri[j]*i]=1;
				if(i%pri[j]==0) break;
			}
		}
		for(LL i=1; i<=r-l+1; ++i) mu[i]=1,x[i]=l+i-1;
		for(RI i=1; i<=tot; ++i)
		{
			LL tmp=1LL*pri[i]*((l-1)/pri[i]+1);
			for(LL j=tmp; j<=r; j+=pri[i])
			{
				if(!mu[j-l+1]) continue;
				mu[j-l+1]=-mu[j-l+1],x[j-l+1]/=pri[i];
				if(x[j-l+1]%pri[i]==0) mu[j-l+1]=0;
			}
		}
		for(LL i=l; i<=r; ++i)
		{
			if(x[i-l+1]!=1)
			{
				if(Miller_Rabin(x[i-l+1],2)) mu[i-l+1]=-mu[i-l+1];
				else
				{
					LL tmp=sqrt((double)x[i-l+1]);
					if(tmp*tmp==x[i-l+1]) mu[i-l+1]=0;
				}
			}
			putchar(mu[i-l+1]==0?'0':(mu[i-l+1]==-1?'-':'+'));
		}
		puts("");
	}
};
namespace work5
{
	int pri[10],tot;
	bool is[13123120],isg[13123120];
	void QAQ1(int l,int r,int P)
	{
		if(P==998244353) tot=3,pri[1]=2,pri[2]=7,pri[3]=17;
		else tot=4,pri[1]=2,pri[2]=3,pri[3]=4003,pri[4]=15773;
		for(RI i=l; i<=r; ++i)
		{
			int flag=1;
			if(qpow(i,P-1,P)!=1) flag=0;
			else
			{
				for(RI j=1; j<=tot; ++j)
					if(qpow(i,(P-1)/pri[j],P)==1)
					{
						flag=0;
						break;
					}
			}
			putchar(flag?'g':'.');
		}
		puts("");
	}
	void QAQ2()
	{
		const int g=6;
		tot=8,pri[1]=2,pri[2]=3,pri[3]=5;
		pri[4]=7,pri[5]=11,pri[6]=13,pri[7]=19,pri[8]=23;
		for(RI i=1; i<=tot; ++i)
			for(RI j=pri[i]; j<=13123110; j+=pri[i]) is[j]=1;
		for(RI i=1,g=6; i<=13123110;
		        ++i,g=6LL*g%13123111) if(!is[i]) isg[g]=1;
		for(RI i=1; i<=13123110; ++i) putchar(isg[i]?'g':'.');
	}
	void work()
	{
		int l,r,P,T;
		cin>>T;
		cin>>l>>r>>P,puts(".g");
		cin>>l>>r>>P,puts(".g.gg...g");
		if(T==4)
		{
			cin>>l>>r>>P,QAQ1(l,r,P);
			cin>>l>>r>>P,QAQ1(l,r,P);
		}
		else
		{
			cin>>l>>r;
			if(l==1) QAQ2();
			else QAQ1(l,r,1515343657);
		}
	}
};
int main()
{
	srand(19260817);
	scanf("%s",typ);
	if(!strcmp(typ,"1_998244353")) work1::work(998244353LL);
	else if(!strcmp(typ,"1?")) work1::work(1145141LL);
	else if(!strcmp(typ,"1?+")) work1::work(5211600617818708273LL);
	else if(!strcmp(typ,"1wa_998244353")) work2::work();
	else if(!strcmp(typ,"2p")) work3::work();
	else if(!strcmp(typ,"2u")) work4::work();
	else work5::work();
	return 0;
}