[ chinese remainder theorem ] 中國剩餘定理

我是看維基百科實現的，所以就直接貼上模板
注意:

• crt函數的m[i]是模數
• crt函數的a[i]是原本數模m[i]後的值
• 必須要保證m兩兩互質
• 容易溢位

模板:

	#ifndef CHINESE_REMAINDER_THEOREM
	#define CHINESE_REMAINDER_THEOREM
	template<typename T>
	inline T Euler(T n){
	T ans=n;
	for(T i=2;i*i<=n;++i){
	if(n%i==0){
	ans=ans/i*(i-1);
	while(n%i==0)n/=i;
	}
	}
	if(n>1)ans=ans/n*(n-1);
	return ans;
	}
	template<typename T>
	inline T pow_mod(T n,T k,T m){
	T ans=1;
	for(n=(n>=m?n%m:n);k;k>>=1){
	if(k&1)ans=ans*n%m;
	n=n*n%m;
	}
	return ans;
	}
	template<typename T>
	inline T crt(std::vector<T> &m,std::vector<T> &a){
	T M=1,tM,ans=0;
	for(int i=0;i<(int)m.size();++i)M*=m[i];
	for(int i=0;i<(int)a.size();++i){
	tM=M/m[i];
	ans=(ans+(a[i]*tM%M)*pow_mod(tM,Euler(m[i])-1,m[i])%M)%M;
	/*如果m[i]是質數，Euler(m[i])-1=m[i]-2，就不用算Euler了*/
	}
	return ans;
	}
	#endif

view raw Chinese remainder theorem.cpp hosted with ❤ by GitHub