「十二省联考 2019」骗分过样例

很显然，这是一道有时限的提答题!!!!

但是知识点很丰富，值得一写

Case 1-3: 1_998244353

直接快速幂$19^x$，如果读入太大，指数可以$\mod \varphi(998244353)$ ,不谈…

Case 4: 1?

不知道模数，但是可以看出模数很小，随便选一个答案试出模数即可(145141?)

Case5: 1?+

值域非常大，就算是快速幂也显然要通过快速乘来实现，设模数为$P$

把所有读入的数拿出来看，发现最相近的两个相差只有$2$

意味着我们知道

$19^x \equiv a\pmod P,19^{x+2} \equiv b \pmod P$

很显然$a\cdot 19^2 \mod P=b$，求出$a\cdot 19^2-b$，分解质因数即可

实际实现可以用手写高精/Python

Case6: 1_wa998244353

答案的生成是，求幂次的时候乘法不开long long ，即

1
2
int n,s=1; scanf("%d",&n);
for(int i=1;i<=n;++i) s=s*19%998244353;

出题人的tips给了，自然溢出是非定义行为，甚至有可能导致RE

所以模拟的话，实际应该这样写

1
s=int(((unsigned)s*19))%P;

可以发现，这个答案的序列近似于一个伪随机数列，学过$\text{Pollard’s Rho}$算法就知道，

根据生日问题/生日悖论，伪随机数列期望在$O(\sqrt n)$的时间内产生一个伪循环，因此可以快速求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int s[300000];
int T=-1,fir=-1;
map <int,int> M;
s[0]=1,M[1]=0;
rep(i,1,300000){
    s[i]=int(((unsigned)s[i-1]*19))%P;
	if(M.count(s[i])) {
		T=i-M[s[i]],fir=M[s[i]];
		break;
	}		
    M[s[i]]=i;
}
rep(kase,1,rd()){
	ll x=rd<ll>();
	printf("%d\n",s[x<=fir?x:(x-fir)%T+fir]);
}

Case8-10: 2p

判断$[l,r]$内的数是否是质数，$\text{Miller_Rabin}$模板

Case9-10: 2u

求$[L,R]$内的莫比乌斯系数$w(n)$，设$n=\prod_1^m p_i^{c_i},c_i>0$

$w(n)=\left\{\begin{aligned} (-1)^m &&\nexists c_i>1,\\ 0 && \exists c_i>1\end{aligned}\right.$

对于$L,R$达到$10^{18}$次时，考虑先用$[1,R^{\frac{1} {3} }]$内的质数筛掉，那么剩下的数最多包含两个$(R^{\frac{1} {3} },R]$内的质因数

可以开根号判断是否是平方数，用$\text{Miller_Rabin}$判断是否是质数

由于$R-L$与$R^{\frac{1} {3} }$同阶复杂度为$O(R^{\frac{1} {3} }\log R^{\frac{1} {3} })$，常数较大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int,int> Pii;
#define pb push_back
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

char IO;
template <class T=int> T rd(){
	T s=0;int f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=1e6+10,P=998244353;

ll qmul(ll x,ll y,ll P){
	ll z=(long double)x/P*y;
	ll t=(ull)x*y-(ull)z*P;
	t=t%P; Mod2(t);
	return t;
}
ll qpow2(ll x,ll k,ll P) {
	ll res=1;
	for(;k;k>>=1,x=qmul(x,x,P)) if(k&1) res=qmul(res,x,P);
	return res;
}
ll qpow(ll x,ll k,ll P) {
	if(P>2e9) return qpow2(x,k,P);
	ll res=1;
	for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
}

char s[20000];
void Solve19(ll P){
	scanf("%s",s+1);
	ll k=0;
	for(int i=1;s[i];++i) k=(qmul(k,10,P-1)+s[i]-'0')%(P-1);
	printf("%lld\n",qpow(19,k,P));
}
int notpri[N],pri[N],pc,w[N];
void Init(){
	notpri[1]=w[1]=1;
	rep(i,2,N-1) {
		if(!notpri[i]) pri[++pc]=i,w[i]=-1;
		for(int j=1;j<=pc && 1ll*i*pri[j]<N;++j){
			notpri[i*pri[j]]=1;
			if(i%pri[j]==0) {
				w[i*pri[j]]=0;
				break;
			}
			w[i*pri[j]]=-w[i];
		}
	}
}
int MR(ll x){
	if(x==2) return 1;
	if(x<=1 || ~x&1) return 0;
	if(x<N) return !notpri[x];
	ll s=0,t=x-1;
	while(~t&1) s++,t>>=1;
	rep(i,1,3) {
		ll b=pri[rand()%pc+1],k;
		b=qpow(b,t,x);
		rep(j,1,s) {
			k=qmul(b,b,x);
			if(k==1 && b!=1 && b!=x-1) return 0;
			b=k;
		}
		if(b!=1) return 0;
	}
	return 1;
}
int chk(ll x){ return x<N?!notpri[x]:MR(x); }
char Mo(int x){ return "-0+"[x+1]; }
int ans[N]; ll a[N];
void QueMobius(ll l,ll r){
	while(l<N && l<=r) putchar(Mo(w[l++]));
	if(l>r) return (void)puts("");
	rep(i,0,r-l) ans[i]=1,a[i]=i+l;
	rep(i,2,N-1) if(!notpri[i]) {
		for(ll j=(l+i-1)/i*i;j<=r;j+=i) {
			ll id=j-l;
			if(!ans[id]) continue;
			ll c=0;
			while(a[id]%i==0) a[id]/=i,c++;
			if(c>1) ans[id]=0;
			else ans[id]*=-1;
		}
	}
	rep(i,0,r-l) if(ans[i] && a[i]>1) {
		ll t=round(sqrt(a[i]));
		if(t*t==a[i]) ans[i]=0;
		else if(chk(a[i])) ans[i]=-ans[i];
	}
	rep(i,0,r-l) putchar(Mo(ans[i]));
	puts("");
}
void Queg(int l,int r,int P){
	int t=P-1;
	vector <int> Fac;
	for(int i=2;i*i<=t;++i) if(t%i==0){
		while(t%i==0) t/=i;
		Fac.pb(i);
	}
	if(t>1) Fac.pb(t); 
	
	if(r!=13123110) {
		rep(i,l,r){
			int f=1;
			for(int j:Fac) if(qpow(i,(P-1)/j,P)==1) { f=0; break; }
			putchar(".g"[f]);
		}
	} else {
		static int mk[13123120];
		static bool copri[13123120];
		int g=1;
		rep(i,l,r){
			int f=1;
			for(int j:Fac) if(qpow(i,(P-1)/j,P)==1) { f=0; break; }
			if(f) { g=i; break; }
		}
		int s=1; mk[1]=0;
		rep(i,1,P-2) s=s*g%P,mk[s]=i;
		copri[0]=1;
		for(int i:Fac) for(int j=i;j<P;j+=i) copri[j]=1;
		rep(i,1,P-1) putchar("g."[copri[mk[i]]]);
	}
	puts("");
}

int main(){
	Init();
	freopen("software.in","r",stdin); freopen("software.out","w",stdout);
	string typ; cin>>typ;
	if(typ=="1_998244353") rep(kase,1,rd()) Solve19(998244353);
	else if(typ=="1?") rep(kase,1,rd()) Solve19(1145141);
	else if(typ=="1?+") rep(kase,1,rd()) Solve19(5211600617818708273);
	else if(typ=="1wa_998244353") {
		static int s[300000];
		int T=-1,fir=-1;
		map <int,int> M;
		s[0]=1,M[1]=0;
		rep(i,1,300000){
			s[i]=int(((unsigned)s[i-1]*19))%P;
			if(M.count(s[i])) {
				T=i-M[s[i]],fir=M[s[i]];
				break;
			}
			M[s[i]]=i;
		}
		rep(kase,1,rd()){
			ll x=rd<ll>();
			printf("%d\n",s[x<=fir?x:(x-fir)%T+fir]);
		}
	} else if(typ=="2p") {
		rep(kase,1,rd()) {
			ll l=rd<ll>(),r=rd<ll>();
			for(ll i=l;i<=r;++i) putchar(chk(i)?'p':'.');
			puts("");
		}
	} else if(typ=="2u") {
		rep(kase,1,rd()) {
			ll l=rd<ll>(),r=rd<ll>();
			QueMobius(l,r);
		}
	} else if(typ=="2g" || typ=="2g?") {
		rep(kase,1,rd()){
			int l=rd(),r=rd();
			int p=1515343657;
			if(l!=233333333) p=rd();
			Queg(l,r,p);
		}
	}
}