Luogu P5285 / LOJ3050 【[十二省联考2019]骗分过样例】

伪提答害死人...(出题人赶快出来挨打!!!)

虽说是考场上全看出来是让干嘛了,然而由于太菜以及不会打表所以GG了,只拿了\(39\)...

经测试,截至\(2019.4.18-11:33\),这份接近10K的代码在洛谷速度rk1,在LOJrk4。

题目大意:

功能对应表:

编号 功能 测试点编号 分值
\(1\_998244353\) 求\(19^x\pmod{998244353}\) \(1-3\) \(4+4+4=12\)
\(1?\) 求\(19^x\pmod{?=1145141}\) \(4\) \(7\)
\(1?+\) 求\(19^x\pmod{?=5211600617818708273}\) \(5\) \(9\)
\(1wa\_998244353\) 求\(19^x\pmod{998244353}\)自然溢出(题目提示) \(6-7\) \(6+7=13\)
\(2p\) 判断质数 \(8-10\) \(4+6+8=18\)
\(2u\) 求\(\mu\) \(11-13\) \(5+6+9=20\)
\(2g/2g?\) 判断原根 \(14-15/16\) \(5+7+9=21\)

为了方便你的阅读,我把测试点编号放在了表格的中间,请你注意这一点。

题目思路:

由于是数论多合一,这个慢慢更qwq。我会尽可能把过程写详细的qwq...

代码什么的等我拿到考场源代码再更吧...懒了懒了qwq...

\(test\ 1-3(1\_998244353)\)

看一下第一个样例不难发现输入前几项是连续正整数,输出是\(19\)的次幂,所以第一个功能就是求\(19^x\),因为功能上写着\(998244353\),试一下就会发现确实是在\(\bmod{998244353}\)意义下的结果,所以第一个功能已经明确了。\(test\ 1\)显然直接乘就行,但是看完\(test\ 2,3\)之后会发现,好像不太简单,\(test\ 2\)里面所有输入都是long long级别的数,而\(test\ 3\)里面所有输入都是\(40\)位左右的数,那么考虑到模数是质数,利用费马小定理/欧拉定理,让指数对\(998244352\)取模即可,然后利用秦九韶算法在\(O(len)\)的复杂度内对指数取模,然后跑快速幂即可。

namespace sub1{//1_998244353
const int MOD=998244353,MMOD=998244352;
char s[50];
int n,len;
long long zs;
long long qpow(long long u,long long v){
long long rep=1;
while(v>0){
if(v&1){
rep=rep*u%MOD;
}
u=u*u%MOD;
v>>=1;
}
return rep;
}
void solve(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%s",s);
len=strlen(s);
zs=0;
for(int j=0;j<len;j++){
zs=zs*10+s[j]-'0';
zs%=MMOD;
}
printf("%lld\n",qpow(19,zs));
}
}
}

\(test\ 4(1?)\)

看一下数据会发现前几项是连续的整数,不过相比前\(3\)个测试点而言,能看得出来模数变小了,显然这个任务的重点在于找到未知的模数。大致看一下输出文件会发现,模数是比较小的数,那么显然可以通过暴力测试的方式得到未知模数。实现起来就是对输出数据求\(\max\),然后从\(\max+1\)开始试,用第\(11\)行的数据检验(第一个大输入),然后很快就能得到模数是\(1145141\),然后采用和\(test\ 1-3\)同样的方式处理即可。

namespace sub2{//1?
const int MOD=1145141;
const int MMOD=MOD-1;
char s[50];
int n,len;
long long zs;
long long qpow(long long u,long long v){
long long rep=1;
while(v>0){
if(v&1){
rep=rep*u%MOD;
}
u=u*u%MOD;
v>>=1;
}
return rep;
}
void solve(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%s",s);
len=strlen(s);
zs=0;
for(int j=0;j<len;j++){
zs=zs*10+s[j]-'0';
zs%=MMOD;
}
printf("%lld\n",qpow(19,zs));
}
}
}

\(test\ 5(1?+)\)

如果采用和\(test\ 4\)相同的思路,会发现模数是\(>5\cdot10^{18}\)的,如此大的模数是不适合用暴力寻找的(事实上用暴力也真的没找到)。所以这个点就需要数论多合一进行珂学计算求模数,求得模数等于\(5211600617818708273\)。

计算过程:

对输入文件中的所有指数排序,找除了\(0-9\)以外的相差最小的两个指数,发现最小相差为\(2\),两个指数分别是\(264708066,264708068\)(对应输入文件中的\(7146\)行和\(9371\)行),则对应的答案在\(7143,9368\)两行,分别为\(1996649514996338529,1589589654696467295\),于是有\(1996649514996338529\times361\equiv1589589654696467295\),设模数为\(p\),则\(1996649514996338529\times361-1589589654696467295=kp(k\in\mathbb{N_+})\),用python算出来应该是\(719200885258981741674=kp(k\in\mathbb{N_+})\),然后进行因数分解,有\(\left\{\begin{array}{lcl}719200885258981741674 &=& 1 \times 719200885258981741674 \\ &=& 2 \times 359600442629490870837 \\ &=& 3 \times 239733628419660580558 \\ &=& 6 \times 119866814209830290279 \\ &=& 23 \times 31269603706912249638 \\ &=& 46 \times 15634801853456124819 \\ &=& 69 \times 10423201235637416546 \\ &=& 138 \times 5211600617818708273 \\\end{array}\right.\) ,然后代入检验得模数是\(5211600617818708273\)。

namespace sub3{//1?+
const long long MOD=5211600617818708273LL;
int n;
int zs;
long long plu(long long u,long long v){
return (long long)(((ull)u+(ull)v)%MOD);
}
long long mul(long long u,long long v){
long long rep=0;
while(v>0){
if(v&1){
rep=plu(rep,u);
}
u=plu(u,u);
v>>=1;
}
return rep;
}
long long qpow(long long u,int v){
long long rep=1;
while(v>0){
if(v&1){
rep=mul(rep,u);
}
u=mul(u,u);
v>>=1;
}
return rep;
}
void solve(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&zs);
printf("%lld\n",qpow(19,zs));
}
}
}

\(test\ 6-7(1wa\_998244353)\)

根据题目的提示,应该用到自然溢出(不然你当提示白给你了),然而考试的时候无论如何也没猜到出题人怎么自然溢出的。不过\(test\ 6\)可以骗到,因为是连续的,所以每次\(\times19\),然后对\(998244353\)取模即可。对于\(test\ 7\),只需要找到其中的循环节即可,然后采取类似欧拉定理的方式对指数进行处理,至于结果,打表输出就好了。

namespace sub4{//1wa_998244353
int n,len;
int ans[101000]={};
long long zs;
void solve(){
for(int i=0,rep=1;i<1e5+1000;i++){
ans[i]=rep;
rep=rep*19%998244353;
}
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&zs);
zs=zs>55244?(55245+((zs-55245)%45699)):zs;
printf("%d\n",ans[(int)zs]);
}
}
}

\(test\ 8-10(2p)\)

当首位变成\(2\)的时候就意味着要换任务了(不然你又当题目提示白给你了),一开始看到数据是毫无头绪的,不过看着看着发现两个数似乎代表区间端点(毕竟输出长度在那儿放着呢),然后看到\(2-10\)的输出是\(pp.p.p...\),然后瞬间就想到可能就是判断质数(背质数表:2,3,5,7,...),仔细看一下输出会发现,越往后\(p\)的分布越稀疏,确认过眼神就是判断质数了。\(test\ 8\)判断的是\(1-10^6\),\(test\ 9\)是\(999999000001-10^{12}\),\(test\ 10\)是\(999999999999000001-10^{18}\)。虽说长度都是\(10^6\),但是这难度显然不同啊。

对于\(test\ 8\),线性筛就足够了。

对于\(test\ 9\),不难发现如果其中的某个数为合数,则在\(10^6\)范围内一定存在一个它的质因子,借此可以利用\(test\ 8\)的线性筛筛出\(10^6\)范围内的质数,然后用这些质数去筛\(test\ 9\)区间内的数。

对于\(test\ 10\),可以考虑直接跑\(Miller-Rabin\)检验,只用\(2,3\)跑正确性就没问题,速度也可以接受。

namespace sub5{//2p
int n;
long long l,r;
long long mul(long long u,long long v,long long MOD){
long long w=(long long)(1.0L*u*v/(1.0L*MOD)),rep=u*v-w*MOD;
rep-=MOD;
while(rep<0){
rep+=MOD;
}
return rep;
}
long long qpow(long long u,long long v,long long MOD){
long long rep=1;
while(v>0){
if(v&1){
rep=mul(rep,u,MOD);
}
u=mul(u,u,MOD);
v>>=1;
}
return rep;
}
bool mr(long long u){
if(u==1){
return 0;
}
int tplist[20]={2,3,5,7,61,24251,19260817};
long long v=u-1,rep,nxt;int rrep=0;
while(!(v&1)){
v>>=1;++rrep;
}
for(int i=0;i<2;i++){
if(u==tplist[i]){
return 1;
}
if(u%tplist[i]==0){
return 0;
}
rep=qpow(tplist[i],v,u);
for(int j=1;j<=rrep;j++){
nxt=mul(rep,rep,u);
if(nxt==1&&rep!=1&&rep!=u-1){
return 0;
}
rep=nxt;
}
if(rep!=1){
return 0;
}
}
return 1;
}
void solve(){
printf("pp.p.p...\np.p...\npp.p.p...p.p..\n");
scanf("%d",&n);
scanf("%d",&n);
scanf("%d",&n);
scanf("%d",&n);
scanf("%d",&n);
scanf("%d",&n);
scanf("%d",&n);
scanf("%lld%lld",&l,&r);
if(r<=1e6){
pre();
for(int i=2;i<=1e6;i++){
notpr[i]?putchar('.'):putchar('p');
}
putchar('\n');
}
else if(r<=1e12){
bool vis[1000010]={};
const long long MIN=999998999999LL;
pre();
int st;
for(int i=1;i<=cntpr;i++){
st=(int)((MIN/pr[i])*pr[i]+pr[i]-MIN);
for(;st<=1e6+1;st+=pr[i]){
vis[st]=1;
}
}
for(int i=1;i<=1e6+1;i++){
vis[i]?putchar('.'):putchar('p');
}
}
else{
for(long long i=999999999999000000LL;i<=1000000000000000000LL;i++){
mr(i)?putchar('p'):putchar('.');
}
}
}
}

\(test\ 11-13(2u)\)

有了\(2p\),那自然可以想到后面又是求什么东西的,看一下数据你会发现,出题人偷懒了,就改了个字母,其他和\(8-10\)完全一样。那看一下输出吧,发现只有\(+-0\),那这不就显然了,就是\(\mu\)啊。

和前面\(2p\)一样,\(test\ 11\)直接线性筛就行了。

对于\(test\ 12\),我们可以参考\(test\ 9\)的思路,一方面判断有没有平方因子,另一方面记录不同的质因子个数,由于可能存在\(>10^6\)的质因子,我们记录每个数在筛过之后的值,初值为本身,被一个质数筛过后值除以当前质数,如果最后值\(>1\)就说明还有\(>10^6\)的质因子,那么不同的质因子个数\(+1\)即可,最后根据是否为质数以及不同的质因子个数求出\(\mu\)值即可。

对于\(test\ 13\),如果跑\(Pollard-Rho\),很不幸...这玩意肯定T飞了。那么考虑参考\(test\ 12\)的思路,先筛\(10^6\)以内的质数,用这些质数筛区间里的数,那么考虑对于剩下的未分解完全的数,这些数没有\(10^6\)以内的质因数,数的大小又不超过\(10^{18}\),所以只有三种可能的形式\(p_1,p_1p_2,p_1^2\),质数可以用\(Miller-Rabin\)测试,平方可以开根测试,用排除法确定两质因子乘积形式。

namespace sub6{//2u
int n;
long long l,r;
long long mul(long long u,long long v,long long MOD){
long long w=(long long)(1.0L*u*v/(1.0L*MOD)),rep=u*v-w*MOD;
rep-=MOD;
while(rep<0){
rep+=MOD;
}
return rep;
}
long long qpow(long long u,long long v,long long MOD){
long long rep=1;
while(v>0){
if(v&1){
rep=mul(rep,u,MOD);
}
u=mul(u,u,MOD);
v>>=1;
}
return rep;
}
bool mr(long long u){
if(u==1){
return 0;
}
int tplist[20]={2,3,5,7,61,24251,19260817};
long long v=u-1,rep,nxt;int rrep=0;
while(!(v&1)){
v>>=1;++rrep;
}
for(int i=0;i<2;i++){
if(u==tplist[i]){
return 1;
}
if(u%tplist[i]==0){
return 0;
}
rep=qpow(tplist[i],v,u);
for(int j=1;j<=rrep;j++){
nxt=mul(rep,rep,u);
if(nxt==1&&rep!=1&&rep!=u-1){
return 0;
}
rep=nxt;
}
if(rep!=1){
return 0;
}
}
return 1;
}
void solve(){
printf("--0-+-00+\n-+-00+\n--0-+-00+-0-++\n");
scanf("%d",&n);
scanf("%d",&n);
scanf("%d",&n);
scanf("%d",&n);
scanf("%d",&n);
scanf("%d",&n);
scanf("%d",&n);
scanf("%lld%lld",&l,&r);
if(r<=1e6){
pre();
for(int i=2;i<=1e6;i++){
if(mu[i]<0){
putchar('-');
}
else if(mu[i]>0){
putchar('+');
}
else{
putchar('0');
}
}
putchar('\n');
}
else if(r<=1e12){
bool sqvis[1000010]={};
const long long MIN=999998999999LL;
pre();
for(int i=1;i<=1e6+1;i++){
num[i]=MIN+i;
}
int st;long long sq;
for(int i=1;i<=cntpr;i++){
sq=1LL*pr[i]*pr[i];
st=(int)((MIN/pr[i])*pr[i]+pr[i]-MIN);
for(;st<=1e6+1;st+=pr[i]){
++mucnt[st];
num[st]/=pr[i];
if(!sqvis[st]){
if((MIN+st)%sq==0){
sqvis[st]=1;
}
}
}
}
for(int i=1;i<=1e6+1;i++){
if(num[i]>1){
++mucnt[i];
}
if(sqvis[i]){
putchar('0');
}
else if(mucnt[i]&1){
putchar('-');
}
else{
putchar('+');
}
}
}
else{
bool sqvis[1000010]={};
const long long MIN=999999999998999999LL;
pre();
for(int i=1;i<=1e6+1;i++){
num[i]=MIN+i;
}
int st;long long sq;
for(int i=1;i<=cntpr;i++){
sq=1LL*pr[i]*pr[i];
st=(int)((MIN/pr[i])*pr[i]+pr[i]-MIN);
for(;st<=1e6+1;st+=pr[i]){
++mucnt[st];
num[st]/=pr[i];
if(!sqvis[st]){
if((MIN+st)%sq==0){
sqvis[st]=1;
}
}
}
}
for(int i=1;i<=1e6+1;i++){
if(num[i]>1){
if(mr(num[i])){
++mucnt[i];
}
else{
long long rep=(long long)sqrt(num[i]);
if(rep*rep==num[i]){
sqvis[i]=1;
}
else{
mucnt[i]+=2;
}
}
}
if(sqvis[i]){
putchar('0');
}
else if(mucnt[i]&1){
putchar('-');
}
else{
putchar('+');
}
}
}
}
}

\(test\ 14-16(2g/2g?)\)

看到\(test\ 14\),不用想,这肯定又是让求啥东西了,分布还十分鬼畜,重点是除了区间还又多给了一个数,然后发现是\(998244353\),再想想这是\(g\)啊,\(3\)还是\(g\),那不用多想了吧,原根跑不掉了。既然实锤是原根了,那问题来了,原根咋判断啊???在这直接讲结论了(因为其他的我也不会),对于有原根的数\(p\),设\(\varphi(p)=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}\),其原根\(g\)满足\(\forall i\in[1,k],g^{\frac{\varphi(p)}{p_i}}\neq1\pmod{p}\)。所以对于\(test\ 14\)暴力检验即可。

对于\(test\ 15\),发现要求\(13123111\)的所有原根,范围\(10^7\),然后\(\varphi(13123111)=13123110=2\times3\times5\times7\times11\times13\times19\times23\),每个数检验\(8\)次,一次\(\log\)复杂度,显然会T啊...那怎么办...考虑到原根的性质,对于质数模数\(p\),\(g^0,g^1,\cdots,g^{p-2}\)在\(\bmod{\ p}\)意义下分别为\(1,2,\cdots,p-1\),对于异于\(g\)的原根\(g'\)一定可以被表示为\(g'=g^k(k\in\mathbb{N_+})\),那么显然\(0,k,2k,\cdots,(p-2)k\)在\(\bmod{\ p-1}\)意义下分别对应\(0,1,\cdots,p-2\)(毕竟都是原根...),所以\(\gcd(k,p-1)=1\)。由此,我们根据输出文件得到\(6\)是最小的原根,所以只需要求所有数在模\(13123111\)意义下以\(6\)为原根的指标,所有指标与\(\varphi(p)=p-1\)互质的数都是原根,互质用类似埃筛的方式实现即可。

namespace sub7{//2g
bool vis[13123123]={};int I[13123123]={};
long long qpow(long long u,int v,int MOD){
long long rep=1;
while(v>0){
if(v&1){
rep=rep*u%MOD;
}
u=u*u%MOD;
v>>=1;
}
return rep;
}
bool check(int u){
if(qpow(u,998244352/2,998244353)==1){
return 0;
}
if(qpow(u,998244352/7,998244353)==1){
return 0;
}
if(qpow(u,998244352/17,998244353)==1){
return 0;
}
return 1;
}
void solve(){
printf(".g\n.g.gg...g\n");
int n;
scanf("%d",&n);
if(n==3){
for(int i=2;i<=13123111;i+=2){
vis[i]|=1;
}
for(int i=3;i<=13123111;i+=3){
vis[i]|=1;
}
for(int i=5;i<=13123111;i+=5){
vis[i]|=1;
}
for(int i=7;i<=13123111;i+=7){
vis[i]|=1;
}
for(int i=11;i<=13123111;i+=11){
vis[i]|=1;
}
for(int i=13;i<=13123111;i+=13){
vis[i]|=1;
}
for(int i=19;i<=13123111;i+=19){
vis[i]|=1;
}
for(int i=23;i<=13123111;i+=23){
vis[i]|=1;
}
for(int i=6,j=1;;i=(int)(6LL*i%13123111),++j){
if(I[i]){
break;
}
I[i]=j;
}
for(int i=1;i<13123111;i++){
vis[I[i]]?putchar('.'):putchar('g');
}
putchar('\n');
}
else{
for(int j=2;j<=400000;j++){
if(check(j)){
putchar('g');
}
else{
putchar('.');
}
}
putchar('\n');
for(int j=104857601;j<=105257600;j++){
if(check(j)){
putchar('g');
}
else{
putchar('.');
}
}
putchar('\n');
}
}
}

对于\(16\),重点在于求模数,提示是一个\(10^9\sim2\cdot10^9\)之间的质数,然后暴力枚举,用Miller-Rabin检验质数,检验原根只考虑\(g^{\frac{\varphi(p)}{2}}\)是否满足条件,取前\(25\)个原根检验,用\(531.9s\)就可以得到唯一解,求得未知的质数为\(1515343657\)。

namespace sub8{//2g?
long long qpow(long long u,int v,int MOD){
long long rep=1;
while(v>0){
if(v&1){
rep=rep*u%MOD;
}
u=u*u%MOD;
v>>=1;
}
return rep;
}
bool check(int u){//1515343656=2*2*2*3*4003*15773
if(qpow(u,1515343656/2,1515343657)==1){
return 0;
}
if(qpow(u,1515343656/3,1515343657)==1){
return 0;
}
if(qpow(u,1515343656/4003,1515343657)==1){
return 0;
}
if(qpow(u,1515343656/15773,1515343657)==1){
return 0;
}
return 1;
}
void solve(){
printf(".g\n.g.gg...g\n");
for(int j=233333333;j<=234133333;j++){
if(check(j)){
putchar('g');
}
else{
putchar('.');
}
}
putchar('\n');
}
}

求模数代码:

#include<bits/stdc++.h>

using namespace std;

long long qpow(long long u,long long v,long long MOD){
long long rep=1;
while(v>0){
if(v&1){
rep=(rep*u)%MOD;
}
u=(u*u)%MOD;
v>>=1;
}
return rep;
} bool mr(long long u){
if(u==1){
return 0;
}
int tplist[20]={2,3,5,7,61,24251,19260817};
long long v=u-1,rep,nxt;int rrep=0;
while(!(v&1)){
v>>=1;++rrep;
}
for(int i=0;i<7;i++){
if(u==tplist[i]){
return 1;
}
if(u%tplist[i]==0){
return 0;
}
rep=qpow(tplist[i],v,u);
for(int j=1;j<=rrep;j++){
nxt=rep*rep%u;
if(nxt==1&&rep!=1&&rep!=u-1){
return 0;
}
rep=nxt;
}
if(rep!=1){
return 0;
}
}
return 1;
} bool ccheck(int u,int p,int MOD){
return qpow(u,p,MOD)!=1;
} bool check(int u,int p){
return ccheck(u,(p-1)/2,p);
}
int main(){
for(int i=1e9+1;i<=2e9;i+=2){//1515343657
if(!mr(i)){
continue;
}
if(!check(233333336,i)){
continue;
}
if(!check(233333337,i)){
continue;
}
if(!check(233333338,i)){
continue;
}
if(!check(233333341,i)){
continue;
}
if(!check(233333342,i)){
continue;
}
if(!check(233333344,i)){
continue;
}
if(!check(233333348,i)){
continue;
}
if(!check(233333351,i)){
continue;
}
if(!check(233333352,i)){
continue;
}
if(!check(233333355,i)){
continue;
}
if(!check(233333357,i)){
continue;
}
if(!check(233333358,i)){
continue;
}
if(!check(233333365,i)){
continue;
}
if(!check(233333366,i)){
continue;
}
if(!check(233333369,i)){
continue;
}
if(!check(233333376,i)){
continue;
}
if(!check(233333377,i)){
continue;
}
if(!check(233333380,i)){
continue;
}
if(!check(233333381,i)){
continue;
}
if(!check(233333385,i)){
continue;
}
if(!check(233333389,i)){
continue;
}
if(!check(233333392,i)){
continue;
}
if(!check(233333394,i)){
continue;
}
if(!check(233333397,i)){
continue;
}
if(!check(233333401,i)){
continue;
}
printf("%d\n",i);
}
return 0;
}

坑终于填完了qwq...

完整AC代码:

#include<cstdio>//T3 2S 512M
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<map>
#define ull unsigned long long using namespace std; char op[20]; bool notpr[1000010]; int pr[1000010],cntpr,mu[1000010],mucnt[1000010]; long long num[1000010]; void pre(){
notpr[0]=notpr[1]=1;
for(int i=2;i<=1000000;i++){
if(!notpr[i]){
pr[++cntpr]=i;
mu[i]=-1;
}
for(int j=1;j<=cntpr&&i*pr[j]<=1e6;j++){
notpr[i*pr[j]]=1;
if(i%pr[j]==0){
break;
}
mu[i*pr[j]]=-mu[i];
}
}
} namespace sub1{//1_998244353
const int MOD=998244353,MMOD=998244352;
char s[50];
int n,len;
long long zs;
long long qpow(long long u,long long v){
long long rep=1;
while(v>0){
if(v&1){
rep=rep*u%MOD;
}
u=u*u%MOD;
v>>=1;
}
return rep;
}
void solve(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%s",s);
len=(int)strlen(s);
zs=0;
for(int j=0;j<len;j++){
zs=zs*10+s[j]-'0';
zs%=MMOD;
}
printf("%lld\n",qpow(19,zs));
}
}
} namespace sub2{//1?
const int MOD=1145141;
const int MMOD=MOD-1;
char s[50];
int n,len;
long long zs;
long long qpow(long long u,long long v){
long long rep=1;
while(v>0){
if(v&1){
rep=rep*u%MOD;
}
u=u*u%MOD;
v>>=1;
}
return rep;
}
void solve(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%s",s);
len=(int)strlen(s);
zs=0;
for(int j=0;j<len;j++){
zs=zs*10+s[j]-'0';
zs%=MMOD;
}
printf("%lld\n",qpow(19,zs));
}
}
} namespace sub3{//1?+
const long long MOD=5211600617818708273LL;
int n;
int zs;
long long plu(long long u,long long v){
return (long long)(((ull)u+(ull)v)%MOD);
}
long long mul(long long u,long long v){
long long rep=0;
while(v>0){
if(v&1){
rep=plu(rep,u);
}
u=plu(u,u);
v>>=1;
}
return rep;
}
long long qpow(long long u,int v){
long long rep=1;
while(v>0){
if(v&1){
rep=mul(rep,u);
}
u=mul(u,u);
v>>=1;
}
return rep;
}
void solve(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&zs);
printf("%lld\n",qpow(19,zs));
}
}
} namespace sub4{//1wa_998244353
int n,len;
int ans[101000]={};
long long zs;
void solve(){
for(int i=0,rep=1;i<1e5+1000;i++){
ans[i]=rep;
rep=rep*19%998244353;
}
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&zs);
zs=zs>55244?(55245+((zs-55245)%45699)):zs;
printf("%d\n",ans[(int)zs]);
}
}
} namespace sub5{//2p
int n;
long long l,r;
long long mul(long long u,long long v,long long MOD){
long long w=(long long)(1.0L*u*v/(1.0L*MOD)),rep=u*v-w*MOD;
rep-=MOD;
while(rep<0){
rep+=MOD;
}
return rep;
}
long long qpow(long long u,long long v,long long MOD){
long long rep=1;
while(v>0){
if(v&1){
rep=mul(rep,u,MOD);
}
u=mul(u,u,MOD);
v>>=1;
}
return rep;
}
bool mr(long long u){
if(u==1){
return 0;
}
int tplist[20]={2,3,5,7,61,24251,19260817};
long long v=u-1,rep,nxt;int rrep=0;
while(!(v&1)){
v>>=1;++rrep;
}
for(int i=0;i<2;i++){
if(u==tplist[i]){
return 1;
}
if(u%tplist[i]==0){
return 0;
}
rep=qpow(tplist[i],v,u);
for(int j=1;j<=rrep;j++){
nxt=mul(rep,rep,u);
if(nxt==1&&rep!=1&&rep!=u-1){
return 0;
}
rep=nxt;
}
if(rep!=1){
return 0;
}
}
return 1;
}
void solve(){
printf("pp.p.p...\np.p...\npp.p.p...p.p..\n");
scanf("%d",&n);
scanf("%d",&n);
scanf("%d",&n);
scanf("%d",&n);
scanf("%d",&n);
scanf("%d",&n);
scanf("%d",&n);
scanf("%lld%lld",&l,&r);
if(r<=1e6){
pre();
for(int i=2;i<=1e6;i++){
notpr[i]?putchar('.'):putchar('p');
}
putchar('\n');
}
else if(r<=1e12){
bool vis[1000010]={};
const long long MIN=999998999999LL;
pre();
int st;
for(int i=1;i<=cntpr;i++){
st=(int)((MIN/pr[i])*pr[i]+pr[i]-MIN);
for(;st<=1e6+1;st+=pr[i]){
vis[st]=1;
}
}
for(int i=1;i<=1e6+1;i++){
vis[i]?putchar('.'):putchar('p');
}
}
else{
for(long long i=999999999999000000LL;i<=1000000000000000000LL;i++){
mr(i)?putchar('p'):putchar('.');
}
}
}
} namespace sub6{//2u
int n;
long long l,r;
long long mul(long long u,long long v,long long MOD){
long long w=(long long)(1.0L*u*v/(1.0L*MOD)),rep=u*v-w*MOD;
rep-=MOD;
while(rep<0){
rep+=MOD;
}
return rep;
}
long long qpow(long long u,long long v,long long MOD){
long long rep=1;
while(v>0){
if(v&1){
rep=mul(rep,u,MOD);
}
u=mul(u,u,MOD);
v>>=1;
}
return rep;
}
bool mr(long long u){
if(u==1){
return 0;
}
int tplist[20]={2,3,5,7,61,24251,19260817};
long long v=u-1,rep,nxt;int rrep=0;
while(!(v&1)){
v>>=1;++rrep;
}
for(int i=0;i<2;i++){
if(u==tplist[i]){
return 1;
}
if(u%tplist[i]==0){
return 0;
}
rep=qpow(tplist[i],v,u);
for(int j=1;j<=rrep;j++){
nxt=mul(rep,rep,u);
if(nxt==1&&rep!=1&&rep!=u-1){
return 0;
}
rep=nxt;
}
if(rep!=1){
return 0;
}
}
return 1;
}
void solve(){
printf("--0-+-00+\n-+-00+\n--0-+-00+-0-++\n");
scanf("%d",&n);
scanf("%d",&n);
scanf("%d",&n);
scanf("%d",&n);
scanf("%d",&n);
scanf("%d",&n);
scanf("%d",&n);
scanf("%lld%lld",&l,&r);
if(r<=1e6){
pre();
for(int i=2;i<=1e6;i++){
if(mu[i]<0){
putchar('-');
}
else if(mu[i]>0){
putchar('+');
}
else{
putchar('0');
}
}
putchar('\n');
}
else if(r<=1e12){
bool sqvis[1000010]={};
const long long MIN=999998999999LL;
pre();
for(int i=1;i<=1e6+1;i++){
num[i]=MIN+i;
}
int st;long long sq;
for(int i=1;i<=cntpr;i++){
sq=1LL*pr[i]*pr[i];
st=(int)((MIN/pr[i])*pr[i]+pr[i]-MIN);
for(;st<=1e6+1;st+=pr[i]){
++mucnt[st];
num[st]/=pr[i];
if(!sqvis[st]){
if((MIN+st)%sq==0){
sqvis[st]=1;
}
}
}
}
for(int i=1;i<=1e6+1;i++){
if(num[i]>1){
++mucnt[i];
}
if(sqvis[i]){
putchar('0');
}
else if(mucnt[i]&1){
putchar('-');
}
else{
putchar('+');
}
}
}
else{
bool sqvis[1000010]={};
const long long MIN=999999999998999999LL;
pre();
for(int i=1;i<=1e6+1;i++){
num[i]=MIN+i;
}
int st;long long sq;
for(int i=1;i<=cntpr;i++){
sq=1LL*pr[i]*pr[i];
st=(int)((MIN/pr[i])*pr[i]+pr[i]-MIN);
for(;st<=1e6+1;st+=pr[i]){
++mucnt[st];
num[st]/=pr[i];
if(!sqvis[st]){
if((MIN+st)%sq==0){
sqvis[st]=1;
}
}
}
}
for(int i=1;i<=1e6+1;i++){
if(num[i]>1){
if(mr(num[i])){
++mucnt[i];
}
else{
long long rep=(long long)sqrt(num[i]);
if(rep*rep==num[i]){
sqvis[i]=1;
}
else{
mucnt[i]+=2;
}
}
}
if(sqvis[i]){
putchar('0');
}
else if(mucnt[i]&1){
putchar('-');
}
else{
putchar('+');
}
}
}
}
} namespace sub7{//2g
bool vis[13123123]={};int I[13123123]={};
long long qpow(long long u,int v,int MOD){
long long rep=1;
while(v>0){
if(v&1){
rep=rep*u%MOD;
}
u=u*u%MOD;
v>>=1;
}
return rep;
}
bool check(int u){
if(qpow(u,998244352/2,998244353)==1){
return 0;
}
if(qpow(u,998244352/7,998244353)==1){
return 0;
}
if(qpow(u,998244352/17,998244353)==1){
return 0;
}
return 1;
}
void solve(){
printf(".g\n.g.gg...g\n");
int n;
scanf("%d",&n);
if(n==3){
for(int i=2;i<=13123111;i+=2){
vis[i]|=1;
}
for(int i=3;i<=13123111;i+=3){
vis[i]|=1;
}
for(int i=5;i<=13123111;i+=5){
vis[i]|=1;
}
for(int i=7;i<=13123111;i+=7){
vis[i]|=1;
}
for(int i=11;i<=13123111;i+=11){
vis[i]|=1;
}
for(int i=13;i<=13123111;i+=13){
vis[i]|=1;
}
for(int i=19;i<=13123111;i+=19){
vis[i]|=1;
}
for(int i=23;i<=13123111;i+=23){
vis[i]|=1;
}
for(int i=6,j=1;;i=(int)(6LL*i%13123111),++j){
if(I[i]){
break;
}
I[i]=j;
}
for(int i=1;i<13123111;i++){
vis[I[i]]?putchar('.'):putchar('g');
}
putchar('\n');
}
else{
for(int j=2;j<=400000;j++){
if(check(j)){
putchar('g');
}
else{
putchar('.');
}
}
putchar('\n');
for(int j=104857601;j<=105257600;j++){
if(check(j)){
putchar('g');
}
else{
putchar('.');
}
}
putchar('\n');
}
}
} namespace sub8{//2g?
long long qpow(long long u,int v,int MOD){
long long rep=1;
while(v>0){
if(v&1){
rep=rep*u%MOD;
}
u=u*u%MOD;
v>>=1;
}
return rep;
}
bool check(int u){//1515343656=2*2*2*3*4003*15773
if(qpow(u,1515343656/2,1515343657)==1){
return 0;
}
if(qpow(u,1515343656/3,1515343657)==1){
return 0;
}
if(qpow(u,1515343656/4003,1515343657)==1){
return 0;
}
if(qpow(u,1515343656/15773,1515343657)==1){
return 0;
}
return 1;
}
void solve(){
printf(".g\n.g.gg...g\n");
for(int j=233333333;j<=234133333;j++){
if(check(j)){
putchar('g');
}
else{
putchar('.');
}
}
putchar('\n');
}
} int main(){
scanf("%s",op);
if(op[0]=='1'){
if(op[1]=='_'){//1_998244353
sub1::solve();
}
else if(op[1]=='?'){
if(op[2]=='+'){//1?+
sub3::solve();
}
else{//1?
sub2::solve();
}
}
else{//1wa_998244353
sub4::solve();
}
}
else{
if(op[1]=='p'){//2p
sub5::solve();
}
else if(op[1]=='u'){//2u
sub6::solve();
}
else{
if(op[2]=='?'){//2g?
sub8::solve();
}
else{//2g
sub7::solve();
}
}
}
return 0;
}
上一篇:hdu6049


下一篇:Hibernate 学习教程