#ifndef Numbertheory_h//數(shù)論知識；
#define Numbertheory_h
#include "Long.h"
#include<stdlib.h>
#include<iostream.h>
#include<string.h>
void Long_to_binary(Long l,char* str){
	l.to_Binary(str);
}
void Long_to_binary(long l,char* str){
   _itoa(l,str,2);
}
template<class Type> Type Square_and_Multiply(Type x,Type b,Type n){//反復(fù)平方乘；Type
	Type z=1;
	char* str=new char[513];
	int i;
	Long_to_binary(b,str);
	int l=strlen(str);
	for(i=0;i<l;i++)
	{
		z=(z*z)%n;
		if (str[i]=='1')
			z=(z*x)%n;
	}
	delete []str;
	return z;
}
template<class Type> Type FactoringAlgorithm(Type n){//素?cái)?shù)因子分解；
	Type sub=2;
	for(sub=2;sub*sub<=n;sub++)
		if((n%sub)==0)
			return sub;
	return 1;
}
template<class Type>
Type MOD(Type x, Type n){//求模運(yùn)算，在Zn范圍內(nèi)
	Type result=x%n;
	if (result<0)
		result=result+n;
	return result;
}
template<class Type>
Type Inverse(Type a,Type n){//求逆運(yùn)算，存在則返回，不存在則返回0
	if(a>n)
		a=MOD(a,n);
	Type r_2=a,r_1=n,r=1;
	Type q,w;
	Type u_2=1;
	Type u_1=0;
	Type u;
	Type v_2=0;
	Type v_1=1;
	Type v;
	while(r!=0)
	{
		
		q=r_2/r_1;r=r_2-q*r_1;
		if(r!=0)
		{u=u_2-q*u_1;v=v_2-q*v_1;r_2=r_1;r_1=r;
		u_2=u_1;u_1=u;v_2=v_1;v_1=v;}
	}
    w=r_1;
	if(w==1)return MOD(u,n);
	else return 0;
}
template<class Type> 
Type sunzi(Type* a,Type* m,int n){//孫子定理
	Type x=1,result=0;
	int i;
	Type* M=new Type[n];
	Type* G=new Type[n];
	for(i=0;i<n;i++)
		x=x*m[i];
	for(i=0;i<n;i++){
		M[i]=x/m[i];
		G[i]=Inverse(M[i],m[i]);
	}
    for(i=0;i<n;i++)
		result+=M[i]*G[i]*a[i];
	result=MOD(result,x);
	delete []M;
	delete []G;
	return result;
}
/*void main(){//主函數(shù)調(diào)用孫子定理的方法；
	//int a[3]={2,3,2};
	//int m[3]={3,5,7};
	//cout<<sunzi(a,m,3)<<endl;
	cout<<MOD(17*22+15*4+9*1,26)<<endl;
	cout<<Inverse(5,26)<<endl;
}*/
int Odd(long int b){//判斷是否為奇數(shù)；
	return b&1;
}
int Odd(Long b){
	return b.Odd();
}
template<class Type>
int Jacobi(Type a,Type n){//計(jì)算Jacobi符號；
	Type two=2;
	Type b;
	Type flg=Odd(n);//(n&1)判斷n是否為正奇數(shù)；
	Type odd=Odd(a);
	if(a==0)return 0;//0這里是判斷合數(shù)的出口；
	else if((a==2)&&(flg==1))//這里的順序呢？
	{
		if(((n%8)==1)||((n%8)==7))
			return 1;
		else return -1;
	}
	else if(odd==0&&flg==1)//(a&1)
	{
		b=a/2;
		return Jacobi(two,n)*Jacobi(b,n);//a/2不能識別，編譯系統(tǒng)真奇怪；
	}
	else if(a>n&&flg==1)
		return Jacobi(a%n,n);//暫時(shí)檢查不到錯(cuò)誤；
	else if(a==1&&flg==1) return 1;//(n&1)調(diào)轉(zhuǎn)一下次序不知道行不行
	//else if(a>n&&flg==1)
		//return Jacobi(a%n,n);//達(dá)唔達(dá)？
	else if(odd==1&&flg==1)
	{
		if((a%4)==3&&(n%4)==3)
			return -Jacobi(n,a);
		else return Jacobi(n,a);
	}
	else return 0;
}
#endif