填一下剩余系相关的数论天坑。

快速求原根

最小的 \(a\) ，满足 \(a\in[2,P-2],\forall p_i|(P-1),a^{p_i}\ne 1\) ，结合欧拉定理即可证明。

BSGS

跟光速幂几乎一个道理，考虑枚举次数 \(\bmod \sqrt{p}\) 的情况，在另一堆中反向找到即可。

CRT

主要是构造一个系数 $m_i=\frac{\prod_{j=1}^{nmod_j}{mod_i},c_i=m_im_i}(\text{模 \(mod_i\) 意义下的逆元})$ ，使得在以 \(mod_i\) 为模数的时候只有该位的 \(r_i\) 做贡献。

exCRT

这个和上面一点关系也没有，主要是考虑利用 exgcd 合并两个限制。

这样通过裴蜀定理判断是否有解，同时更新新的 \(R'=p\cdot MOD+R\) 和 \(MOD'=\text{lcm}(MOD,mod_i)\) 即可。

P2480 [SDOI2010]古代猪文

考虑到 \(99911658=2\times3\times 4679\times 35617\) ，我们可以用卢卡斯定理求出每一个质因数的答案，然后用 exCRT 合并一波即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=999911659;
const int MOD[4]={2,3,4679,35617};
int ksm(int x,int k,int MOD,int res=1){
	for(;k;k>>=1,x=x*x%MOD) if(k&1) res=res*x%MOD;
	return res;
}
int fact[4][35617],ifact[4][35617];
int n,g,res=0;
int exgcd(int a,int b,int &x,int &y){
	if(!b) return x=1,y=0,a;
	int _x,_y,tmp=exgcd(b,a%b,_x,_y);
	return x=_y,y=_x-a/b*_y,tmp;
}
int C(int c,int n,int m){
	if(n<0||m<0||n-m<0) return 0;
	return ifact[c][m]*ifact[c][n-m]%MOD[c]*fact[c][n]%MOD[c];
}
int Lucas(int c,int n,int m){
	if(n<0||m<0||n-m<0) return 0;
	if(n<MOD[c]&&m<MOD[c]) return C(c,n,m);
	return C(c,n%MOD[c],m%MOD[c])*Lucas(c,n/MOD[c],m/MOD[c])%MOD[c];
}
int cal(int k){
	int R[4],mod=1,r=0;
	for(int c=0;c<4;++c) R[c]=Lucas(c,n,k);
	for(int c=0;c<4;++c){
		int x,y,tmp=exgcd(mod,MOD[c],x,y);
		x=x*(R[c]-r)/tmp%MOD[c],r+=x*mod;
		mod*=MOD[c]/tmp,r=(r%mod+mod)%mod;
	}
	return r;
}
signed main(){
	for(int c=0;c<4;++c){
		fact[c][0]=1;
		for(int i=1;i<MOD[c];++i) fact[c][i]=fact[c][i-1]*i%MOD[c];
		ifact[c][MOD[c]-1]=ksm(fact[c][MOD[c]-1],MOD[c]-2,MOD[c]);
		for(int i=MOD[c]-1;i>=1;--i) ifact[c][i-1]=ifact[c][i]*i%MOD[c];
	}
	cin>>n>>g;
	if(g==999911659) return printf("0\n"),0;
	for(int i=1;i*i<=n;++i){
		if(n%i) continue;
		(res+=cal(i))%=mod-1;
		if(i*i!=n) (res+=cal(n/i))%=mod-1;
	}
	return printf("%lld\n",ksm(g,res,mod)),0;
}

P4774 [NOI2018] 屠龙勇士

我好像不会做捏。

巨龙的击杀顺序是固定的，所以你这个换剑有个啥用啊。首先我们必然可以预处理出每一条巨龙所对应的剑，然后我们即需要求一个最小的 \(x\) 满足

首先我们可以找到对于每条巨龙最小的 \(x\) 及变大的公差，等差数列求交？等差数列是不是都可以化成一个取模式，直接用 exCRT 求解即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int n,m;
int a[N],b[N],z[N];
int MOD,R,limit=0;
multiset<int> bag;
int exgcd(int a,int b,int &x,int &y){
	if(!b) return x=1,y=0,a;
	int _x,_y,tmp=exgcd(b,a%b,_x,_y);
	return x=_y,y=_x-a/b*_y,tmp;
}
int solve(){
	cin>>n>>m,bag.clear();
	for(int i=1;i<=n;++i) scanf("%lld",&z[i]);
	for(int i=1;i<=n;++i) scanf("%lld",&b[i]);
	for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
	for(int i=1,x;i<=m;++i) scanf("%lld",&x),bag.insert(x);
	for(int i=1;i<=n;++i){
		auto tmp=bag.upper_bound(z[i]);
		if(tmp!=bag.begin()) tmp--;
		bag.insert(a[i]),a[i]=*tmp,bag.erase(tmp);
	}
	MOD=1,R=0,limit=0;
	for(int i=1;i<=n;++i){
		int x,y,tmp=exgcd(a[i],b[i],x,y);
		if(z[i]%tmp) return printf("-1\n"),0;
		limit=max(limit,(z[i]-1)/a[i]+1);
		int mod=b[i]/tmp,r=((__int128)x*z[i]/tmp%mod+mod)%mod;
		// printf("! %lld %lld\n",mod[i],r[i]);
		tmp=exgcd(MOD,mod,x,y);
		if((r-R)%tmp) return printf("-1\n"),0;
		x=(__int128)x*(r-R)/tmp%mod;
		R+=(__int128)x*MOD%(MOD/tmp*mod),MOD*=mod/tmp,R=(R%MOD+MOD)%MOD;
	}
	if(R>=limit) return printf("%lld\n",R),0;
	return printf("%lld\n",((limit-R-1)/MOD+1)*MOD+R),0;
}
signed main(){
	freopen("dragon.in","r",stdin);
	freopen("dragon.out","w",stdout);
	int T;cin>>T;while(T--) solve();
	return 0;
}