【模板】数学

int bsgs(int a,int b,int p){//(a^x)%p=b%p 
	map<int,int> ha;
	int t=sqrt(p)+1;
	for(int i=0,q=b%p;i<t;++i,q=q*a%p)	ha[q]=i;
	int w=ksm(a,t,p);
	for(int i=1,q=w;i<=t;++i,q=q*w%p)
		if(ha.find(q)!=ha.end())	return t*i-ha[q];
	return -1;
}

int bsgs(int a,int b,int p,int ad){
	unordered_map<int,int> ha;
	int t=sqrt(p)+1;
	for(int i=0,j=b%p;i<t;++i,j=j*a%p)	ha[j]=i;
	int w=ksm(a,t,p);
	for(int i=1,j=ad*w%p;i<=t;++i,j=j*w%p)
		if(ha.find(j)!=ha.end())	return i*t-ha[j];
	return -1;
}
int exbsgs(int a,int b,int p){
	a%=p,b%=p;
	int cnt=0,ad=1,t;
	if(b==1 || p==1)	return 0;
	while((t=__gcd(a,p))!=1){
		if(b%t!=0)	return -1;
		++cnt,b/=t,p/=t,ad=ad*(a/t)%p;
		if(ad==b)	return cnt;
	}
	t=bsgs(a,b,p,ad);return (t==-1?-1:t+cnt);
}

int CRT(){
	int m=1,res=0,x,y;
	for(int i=1;i<=n;++i)	m*=a[i];
	for(int i=1;i<=n;++i){
		int tmp=m/a[i];
		exgcd(tmp,a[i],x,y);
		res=(res+tmp*x*b[i]%m)%m;
	}
	return (res%m+m)%m;
}

const int N=1e5+5;
int a[N],b[N],n;
int exgcd(int a,int b,int &x,int &y){
	if(!b){x=1,y=0;return a;}
	int g=exgcd(b,a%b,x,y),t=x;
	x=y,y=t-a/b*y;
	return g;
}
int excrt(){
	int A=a[1],B=b[1];
	for(int i=2;i<=n;++i){
		int k1,k2;
		int g=exgcd(A,a[i],k1,k2);
		if((b[i]-B)%g!=0)	return -1;
		k1*=(b[i]-B)/g;
		k1=(k1%(a[i]/g)+(a[i]/g))%(a[i]/g);
		B=k1*A+B,A=(A*a[i])/g;
	}
	return B%A;
}

void Guass(){
	for(int i=1;i<=n;++i){
		int ma=i;
		for(int j=i+1;j<=n;++j)if(fabs(a[j][i])>fabs(a[ma][i]))ma=j;
		if(i!=ma)	swap(a[i],a[ma]);
		if(fabs(a[i][i])<eps){cout<<"No Solution\n";return;}
		d div=a[i][i];
		for(int j=i;j<=n+1;++j)	a[i][j]/=div;
		for(int j=i+1;j<=n;++j){
			div=a[j][i];
			for(int k=i;k<=n+1;++k)	a[j][k]-=div*a[i][k];
		}
	}
	for(int i=n;i;--i){
		ans[i]=a[i][n+1];
		for(int j=i-1;j;--j)a[j][n+1]-=(a[j][i]*ans[i]);
	}
	for(int i=1;i<=n;++i)printf("%.2lf\n",ans[i]);
}

void Guass_Jordan(){
	for(int i=1;i<=n;++i){
		int ma=i;
		for(int j=i+1;j<=n;++j)if(fabs(a[j][i])>fabs(a[ma][i]))ma=j;
		for(int j=1;j<=n+1;++j)swap(a[i][j],a[ma][j]);
		// cout<<ma<<" : ";
		if(fabs(a[i][i])<eps){cout<<"No Solution";return;}
		for(int j=1;j<=n;++j){
			if(j==i)	continue;
			for(int k=i+1;k<=n+1;++k)a[j][k]-=a[i][k]*a[j][i]/a[i][i];
		}
	}
	for(int i=1;i<=n;++i)printf("%.2lf\n",a[i][n+1]/a[i][i]);
}

int exgcd(int a,int b,int &x,int &y){
	if(!b){x=1,y=0;return a;}
	int g=exgcd(b,a%b,x,y),t=x;
	x=y,y=t-a/b*y;
	return g;
}

void init(int n){
	for(int i=2;i<=n;++i){
		if(!vi[i])	pr[++co]=i,phi[i]=i-1;
		for(int j=1;j<=co && i*pr[j]<=n;++j){
			vi[pr[j]*i]=1;
			if(i%pr[j]==0){
				phi[pr[j]*i]=phi[i]*pr[j];
				break;
			}
			else	phi[i*pr[j]]=phi[i]*(pr[j]-1);
		}
	} 
}