1_998244353：
由于(998244353)是十分常见的模数，所以可以猜想到取模。
(1,19,361....)是(19^x)。
前两个点可以直接用快速幂计算。
第三个点由于数比较大，所以使用euler定理，把幂次模(998244352)后快速幂。
namespace s1{
int mo=998244353;
int qp(int x,int y){
int r=1;
for(;y;y>>=1,x=x*x%mo)
if(y&1)
r=r*x%mo;
return r;
}
int rd(){
char c=getchar();
int x=0;
while(!isdigit(c))
c=getchar();
while(isdigit(c)){
x=(x*10%(mo-1)+c-'0')%(mo-1);
c=getchar();
}
return x;
}
void main(){
int T;
scanf("%lld",&T);
while(T--){
int x=rd();
printf("%lld
",qp(19,x));
}
}
};
1_?：
发现前3个数是(1,19,361)，而且是联考年份的尾数，所以考虑快速幂。
由于取模的性质，所以每个数都会小于模数，可以从答案文件最大数开始暴力从小到大枚举。
在验证时只需要验证第一个数即可。
发现是(1145141)
namespace s2{
int mo=1145141;
int qp(int x,int y){
int r=1;
for(;y;y>>=1,x=x*x%mo)
if(y&1)
r=r*x%mo;
return r;
}
int rd(){
char c=getchar();
int x=0;
while(!isdigit(c))
c=getchar();
while(isdigit(c)){
x=(x*10%(mo-1)+c-'0')%(mo-1);
c=getchar();
}
return x;
}
void main(){
int T;
scanf("%lld",&T);
while(T--){
int x=rd();
printf("%lld
",qp(19,x));
}
}
};
1_?+：
由于很多数都大于(998244353)，所以模数肯定不是(998244353)，要试。
由于模数比较大，暴力试不可取。
考虑取出两个数(x,y(x<y))，使得(19^xmod p=a,19^ymod p=b)，且(a>b)
则(19^{y-x}a-b=kP)（(k)是正整数）
这样子我们确定了(P)是某个数的约数，然后枚举这个数的约数即可。
经枚举发现是(5211600617818708273)
注意快速乘
namespace s3{
int mo=5211600617818708273;
int ml(int x,int y,int m){
int r=x*y-(int)((long double)x*y/m+0.5)*m;
return r<0?r+m:r;
}
int qp(int x,int y){
int r=1;
for(;y;y>>=1,x=ml(x,x,mo))
if(y&1)
r=ml(r,x,mo);
return r;
}
int rd(){
char c=getchar();
int x=0;
while(!isdigit(c))
c=getchar();
while(isdigit(c)){
x=(x*10%(mo-1)+c-'0')%(mo-1);
c=getchar();
}
return x;
}
void main(){
int T;
scanf("%lld",&T);
while(T--){
int x=rd();
printf("%lld
",qp(19,x));
}
}
};
1wa_998244353：
由于(998244353)是十分常见的模数，所以可以猜想到取模。
由于出现负数，可以猜想是自然溢出。
自然溢出的方式是一个一个乘，而不是快速幂。
第一个点可以暴力。
第二个点由于输入非常大不能暴力。
但是由于生日悖论，所以循环节比较短，可以用map寻找。
namespace s4{
signed mo=998244353,zq,db[2000010],st;
map<int,int>ma;
void gt(){
signed x=1;
ma[x]=0;
int c=0;
db[0]=1;
while(1){
c++;
x=x*19%mo;
db[c]=x;
if(ma.count(x)){
st=ma[x];
zq=c-ma[x];
break;
}
ma[x]=c;
}
}
int rd(){
char c=getchar();
int x=0;
while(!isdigit(c))
c=getchar();
while(isdigit(c)){
x=(x*10%(mo-1)+c-'0')%(mo-1);
c=getchar();
}
return x;
}
void main(){
gt();
int T;
scanf("%lld",&T);
while(T--){
int x;
scanf("%lld",&x);
if(x<st)
printf("%d
",db[x]);
else
printf("%d
",db[(x-st)%zq+st]);
}
}
};
可以猜想以(1)开头的测试点和(19^x)有关。
2p：
由于和数论相关，所以猜想(p)是质数。
发现问题就是判定区间每个数是否是素数。
第一个点可以直接线性筛。
第二个点可以区间筛：有一经典结论是一个数最多只有一个(>sqrt{n})的素因子，所以可以把(leq sqrt{n})的素数拿出来筛区间。
第三个点可以直接miller_rabin。
namespace s5{
int ml(int x,int y,int m){
int r=x*y-(int)((long double)x*y/m+0.5)*m;
return r<0?r+m:r;
}
int qp(int x,int y,int m){
int r=1;
for(;y;y>>=1,x=ml(x,x,m))
if(y&1)r=ml(r,x,m);
return r;
}
int mr(int a,int b){
int k=a-1;
while(k){
int v=qp(b,k,a);
if(v!=1&&v!=a-1)return 0;
if((k&1)==1||v==a-1)return 1;
k>>=1;
}
return 1;
}
int cp(int a){
if(a<10000000)
return !vi[a];
for(int i=1;i<=30;i++)
if(a%p[i]==0)
return 0;
return mr(a,2)&&mr(a,3)&&mr(a,5)&&mr(a,7)&&mr(a,10007);
}
void main(){
int T;
scanf("%lld",&T);
while(T--){
int l,r;
scanf("%lld%lld",&l,&r);
for(int i=l;i<=r;i++){
if(cp(i))
printf("p");
else
printf(".");
}
puts("");
}
}
};
2u：
根据前面的经验，类别的第一个字符如果是(1)，则问题和(19^x)有关，否则和区间有关。
由于输出只有(3)种，猜想是莫比乌斯函数。
第一个点可以直接线性筛。
第二个点可以区间筛。
第三个点pollard_rho会爆掉。
还是考虑区间筛，筛出(leq n的立方根)的素数。
然后把区间内的所有数的(leq n的立方根)的素数都去掉，并且累加贡献。
类比前面的结论，发现区间内每个数留下来的因子都是(>n的立方根)的，最多只有(2)个。
使用miller_rabin判定素数，如果是素数，则答案取反，如果存在两个相同的素因子（用sqrt判定），则答案为(0)。
否则两个素数的贡献抵消，答案不变。
namespace s6{
int v[N];
int ml(int x,int y,int m){
int r=x*y-(int)((long double)x*y/m+0.5)*m;
return r<0?r+m:r;
}
int qp(int x,int y,int m){
int r=1;
for(;y;y>>=1,x=ml(x,x,m))
if(y&1)r=ml(r,x,m);
return r;
}
int mr(int a,int b){
int k=a-1;
while(k){
int v=qp(b,k,a);
if(v!=1&&v!=a-1)return 0;
if((k&1)==1||v==a-1)return 1;
k>>=1;
}
return 1;
}
int cp(int a){
if(a==46856248255981ll||a<2)return 0;
if(a==2||a==3||a==7||a==61||a==24251)return 1;
return mr(a,2)&&mr(a,61);
}
void main(){
int T;
scanf("%lld",&T);
while(T--){
int l,r;
scanf("%lld%lld",&l,&r);
for(int i=l;i<=r;i++){
v[i-l+1]=i;
u[i-l+1]=1;
}
for(int i=1;i<=ct;i++){
int x=p[i];
for(int j=x*((l-1)/x+1)-l+1;j<=r-l+1;j+=x){
if(v[j]%(x*x)==0)
u[j]=0;
else{
v[j]/=x;
u[j]=-u[j];
}
}
}
for(int i=1;i<=r-l+1;i++){
int x=v[i];
if(u[i]&&x>1){
int va=sqrt(x);
if(va*va==x)
u[i]=0;
if(x<=1e14||cp(v[i]))
u[i]=-u[i];
}
if(!u[i])
printf("0");
else if(u[i]==1)
printf("+");
else
printf("-");
}
puts("");
}
}
};
2g：
根据前面的经验，我们要求出区间内的每个数是否是原根，并且输出。
第一个点可以按照原根的判定定理求。
由于模数(=998244353)，素因子个数较少，所以可以分解(998244352)，然后枚举每个素因子试除判定。
第二个点模数（相对第一个点）较小，而且在(1e7)级别，可以存下。
考虑求出模数下的每个原根，找到任一个原根(g)。
这可以暴力枚举(<p)的所有数。
一个结论是：一个数的最小原根是它的四次方根级别，所以时间复杂度可以忍受。
此部分时间复杂度大约是(O(sqrt{sqrt{P}}c(P)log_2P))，(c)是素数个数函数。
找到原根后，把所有其他数使用原根的幂次表示。
设某个数(v)能够表示成(g^x)。
如果((x,p-1)
eq 1)，则(v^{x/(x,p-1)}=1)，这和原根判定定理矛盾。
(x)不能用bsgs求。
考虑求出每个数模(P)的指标，设为(s)，则(g^{s}=v(mod p))
根据辗转相减，(g)的((s,p-1))次方也是原根
所以当((s,p-1)=1)时才合法。
在实现时，把(p-1)的所有约数（可能的gcd）打上标记，当指标位置没有标记时才合法。
求指标可以线性。从小到大枚举指数即可
namespace s7{
int pr[1000],ct,vi[N*2],va[N*2];
int ml(int x,int y,int m){
int r=x*y-(int)((long double)x*y/m+0.5)*m;
return r<0?r+m:r;
}
int qp(int x,int y,int m){
int r=1;
for(;y;y>>=1,x=ml(x,x,m))
if(y&1)r=ml(r,x,m);
return r;
}
void div(int x){
for(int i=2;i*i<=x;i++)
if(x%i==0){
while(x%i==0)
x/=i;
pr[++ct]=i;
}
if(x!=1)
pr[++ct]=x;
}
int pd(int x,int p){
for(int i=1;i<=ct;i++)
if(qp(x,(p-1)/pr[i],p)==1)
return 0;
return 1;
}
void main(){
int T;
scanf("%lld",&T);
while(T--){
memset(vi,0,sizeof(vi));
int l,r,p;
ct=0;
scanf("%lld%lld%lld",&l,&r,&p);
if(r==234133333)
p=1515343657;
if(r-l+1<=1e6){
div(p-1);
for(int i=l;i<=r;i++){
if(pd(i,p))
printf("g");
else
printf(".");
}
}
else{
div(p-1);
int g=0;
for(int i=1;i<=ct;i++)
for(int j=1;j*pr[i]<p;j++)
vi[pr[i]*j]=1;
for(int i=1;;i++)
if(pd(i,p)){
g=i;
break;
}
int c=1;
for(int i=g;!va[i];i=i*g%p){
va[i]=c;
c++;
}
for(int i=l;i<=r;i++){
if(vi[va[i]])
printf(".");
else
printf("g");
}
}
puts("");
}
}
}
2g?：
由于1?是猜模数，所以这个点也是猜模数。
根据提示，模数一定是(1e9~2e9)之间的一个素数。
所以可以暴力枚举求得。
经枚举发现是(1515343657)。
此时直接套用2g的做法即可。
实际上，题目的每个功能对应的字符串，(1)开头为计算(19)的幂次，(2)开头为求区间的函数值。
完整代码：
#include<bits/stdc++.h>
using namespace std;
#define N 10000010
#define int long long
char s[N];
int ct,p[N],vi[N],u[N];
void si(){
for(int i=2;i<N;i++){
if(!vi[i])
p[++ct]=i;
for(int j=1;j<=ct&&i*p[j]<N;j++){
vi[i*p[j]]=1;
if(i%p[j]==0)
break;
}
}
}
namespace s1{
int mo=998244353;
int qp(int x,int y){
int r=1;
for(;y;y>>=1,x=x*x%mo)
if(y&1)
r=r*x%mo;
return r;
}
int rd(){
char c=getchar();
int x=0;
while(!isdigit(c))
c=getchar();
while(isdigit(c)){
x=(x*10%(mo-1)+c-'0')%(mo-1);
c=getchar();
}
return x;
}
void main(){
int T;
scanf("%lld",&T);
while(T--){
int x=rd();
printf("%lld
",qp(19,x));
}
}
};
namespace s2{
int mo=1145141;
int qp(int x,int y){
int r=1;
for(;y;y>>=1,x=x*x%mo)
if(y&1)
r=r*x%mo;
return r;
}
int rd(){
char c=getchar();
int x=0;
while(!isdigit(c))
c=getchar();
while(isdigit(c)){
x=(x*10%(mo-1)+c-'0')%(mo-1);
c=getchar();
}
return x;
}
void main(){
int T;
scanf("%lld",&T);
while(T--){
int x=rd();
printf("%lld
",qp(19,x));
}
}
};
namespace s3{
int mo=5211600617818708273;
int ml(int x,int y,int m){
int r=x*y-(int)((long double)x*y/m+0.5)*m;
return r<0?r+m:r;
}
int qp(int x,int y){
int r=1;
for(;y;y>>=1,x=ml(x,x,mo))
if(y&1)
r=ml(r,x,mo);
return r;
}
int rd(){
char c=getchar();
int x=0;
while(!isdigit(c))
c=getchar();
while(isdigit(c)){
x=(x*10%(mo-1)+c-'0')%(mo-1);
c=getchar();
}
return x;
}
void main(){
int T;
scanf("%lld",&T);
while(T--){
int x=rd();
printf("%lld
",qp(19,x));
}
}
};
namespace s4{
signed mo=998244353,zq,db[2000010],st;
map<int,int>ma;
void gt(){
signed x=1;
ma[x]=0;
int c=0;
db[0]=1;
while(1){
c++;
x=x*19%mo;
db[c]=x;
if(ma.count(x)){
st=ma[x];
zq=c-ma[x];
break;
}
ma[x]=c;
}
}
int rd(){
char c=getchar();
int x=0;
while(!isdigit(c))
c=getchar();
while(isdigit(c)){
x=(x*10%(mo-1)+c-'0')%(mo-1);
c=getchar();
}
return x;
}
void main(){
gt();
int T;
scanf("%lld",&T);
while(T--){
int x;
scanf("%lld",&x);
if(x<st)
printf("%d
",db[x]);
else
printf("%d
",db[(x-st)%zq+st]);
}
}
};
namespace s5{
int ml(int x,int y,int m){
int r=x*y-(int)((long double)x*y/m+0.5)*m;
return r<0?r+m:r;
}
int qp(int x,int y,int m){
int r=1;
for(;y;y>>=1,x=ml(x,x,m))
if(y&1)r=ml(r,x,m);
return r;
}
int mr(int a,int b){
int k=a-1;
while(k){
int v=qp(b,k,a);
if(v!=1&&v!=a-1)return 0;
if((k&1)==1||v==a-1)return 1;
k>>=1;
}
return 1;
}
int cp(int a){
if(a<10000000)
return !vi[a];
for(int i=1;i<=30;i++)
if(a%p[i]==0)
return 0;
return mr(a,2)&&mr(a,3)&&mr(a,5)&&mr(a,7)&&mr(a,10007);
}
void main(){
int T;
scanf("%lld",&T);
while(T--){
int l,r;
scanf("%lld%lld",&l,&r);
for(int i=l;i<=r;i++){
if(cp(i))
printf("p");
else
printf(".");
}
puts("");
}
}
};
namespace s6{
int v[N];
int ml(int x,int y,int m){
int r=x*y-(int)((long double)x*y/m+0.5)*m;
return r<0?r+m:r;
}
int qp(int x,int y,int m){
int r=1;
for(;y;y>>=1,x=ml(x,x,m))
if(y&1)r=ml(r,x,m);
return r;
}
int mr(int a,int b){
int k=a-1;
while(k){
int v=qp(b,k,a);
if(v!=1&&v!=a-1)return 0;
if((k&1)==1||v==a-1)return 1;
k>>=1;
}
return 1;
}
int cp(int a){
if(a==46856248255981ll||a<2)return 0;
if(a==2||a==3||a==7||a==61||a==24251)return 1;
return mr(a,2)&&mr(a,61);
}
void main(){
int T;
scanf("%lld",&T);
while(T--){
int l,r;
scanf("%lld%lld",&l,&r);
for(int i=l;i<=r;i++){
v[i-l+1]=i;
u[i-l+1]=1;
}
for(int i=1;i<=ct;i++){
int x=p[i];
for(int j=x*((l-1)/x+1)-l+1;j<=r-l+1;j+=x){
if(v[j]%(x*x)==0)
u[j]=0;
else{
v[j]/=x;
u[j]=-u[j];
}
}
}
for(int i=1;i<=r-l+1;i++){
int x=v[i];
if(u[i]&&x>1){
int va=sqrt(x);
if(va*va==x)
u[i]=0;
if(x<=1e14||cp(v[i]))
u[i]=-u[i];
}
if(!u[i])
printf("0");
else if(u[i]==1)
printf("+");
else
printf("-");
}
puts("");
}
}
};
namespace s7{
int pr[1000],ct,vi[N*2],va[N*2];
int ml(int x,int y,int m){
int r=x*y-(int)((long double)x*y/m+0.5)*m;
return r<0?r+m:r;
}
int qp(int x,int y,int m){
int r=1;
for(;y;y>>=1,x=ml(x,x,m))
if(y&1)r=ml(r,x,m);
return r;
}
void div(int x){
for(int i=2;i*i<=x;i++)
if(x%i==0){
while(x%i==0)
x/=i;
pr[++ct]=i;
}
if(x!=1)
pr[++ct]=x;
}
int pd(int x,int p){
for(int i=1;i<=ct;i++)
if(qp(x,(p-1)/pr[i],p)==1)
return 0;
return 1;
}
void main(){
int T;
scanf("%lld",&T);
while(T--){
memset(vi,0,sizeof(vi));
int l,r,p;
ct=0;
scanf("%lld%lld%lld",&l,&r,&p);
if(r==234133333)
p=1515343657;
if(r-l+1<=1e6){
div(p-1);
for(int i=l;i<=r;i++){
if(pd(i,p))
printf("g");
else
printf(".");
}
}
else{
div(p-1);
int g=0;
for(int i=1;i<=ct;i++)
for(int j=1;j*pr[i]<p;j++)
vi[pr[i]*j]=1;
for(int i=1;;i++)
if(pd(i,p)){
g=i;
break;
}
int c=1;
for(int i=g;!va[i];i=i*g%p){
va[i]=c;
c++;
}
for(int i=l;i<=r;i++){
if(vi[va[i]])
printf(".");
else
printf("g");
}
}
puts("");
}
}
}
signed main(){
scanf("%s",s);
si();
if(s[0]=='1'&&s[1]=='_'){
s1::main();
return 0;
}
if(s[0]=='1'&&s[1]=='?'&&s[2]=='+'){
s3::main();
return 0;
}
if(s[0]=='1'&&s[1]=='?'){
s2::main();
return 0;
}
if(s[0]=='1'&&s[1]=='w'){
s4::main();
return 0;
}
if(s[0]=='2'&&s[1]=='p'){
s5::main();
return 0;
}
if(s[0]=='2'&&s[1]=='u'){
s6::main();
return 0;
}
if(s[0]=='2'&&s[1]=='g'){
s7::main();
return 0;
}
}