数论模板2次.cpp

ACM 算法模板,适合搞ACM的人

#include<iostream>
#include<cmath>
using namespace std;
//数论模板
//辗转相除法求最大公约数
long gcd(long a, long b)
{
     if(b==0)
		 return a;
	 else
		 return gcd(b,a%b);
}
//求最大公倍数
long lcm(long a, long b)
{
	if(a*b==0) return 0;
	else
		return a*b/gcd(a,b);
}
//求a^b mod n
long modexp(long a, long b, long n)
{
    int t, y;
	t=1; y=a;
	while(b!=0)
	{
	   if(b&1==1)
		   t=t*y%n;
	   y=y*y%n;
	   b/=2;
	}
	return t;
}
//扩展的Euclid算法
//返回a.b的最大公约数， 并使ax+by=d;
long exEuclid(long a, long b, long & x, long & y)
{ 
	long tmp,d;
	if(b==0)
	{
		x=1;
		y=0;
		return a;
	}
	d=exEuclid(b, a%b, x,y);
	tmp=x;
	x=y;
	y=tmp-a/b*y;
    return d;
}
//解线性同余方程ax=b(mod n)
//返回最小的x
long  modu(long a, long b, long n)
{
     long d,x=1,y=0;
	 d=exEuclid(a,n,x,y);
	 x=x*(b/d);
	 x=(x%(n/d)+n/d)%(n/d);
	 return x;
}
//用中国剩余定理解同余方程组a=bi（modni)
long solmodu(long z, long b[], long n[])
{   
	int i;
    long a,m,x,y,t;
	m=1 ;a=0;
	for(i=0; i<z; i++)  m*=n[i];
	for(i=0; i<z; i++)
    {
		t=m/n[i];
		exEuclid(n[i],t,x,y);
		a=(a+t*y*b[i])%m;
	}
	return (a+m)%m;
}
//筛法求素数
const maxn=100000;
bool  prime[maxn+1];
void  searchprime(long b[],long & k)
{
   int i ,j;
   memset(prime,0,sizeof(prime));
   prime[1]=1;
   for(i=2; i<sqrt(maxn); i++)
	   if(!prime[i])
	   {
          j=i*2;
		  while(j<=maxn)
		  {
			  prime[j]=1;
			  j+=i;
		  }
	   }
  j=0;
  for(i=1; i<maxn; i++)
	  if(prime[i]==0)
		     b[j++]=i;
   k=j;
}
//判定素数 素数表
bool isPrime(long x,long b[])
{
	int i;
	i=1;
	while(b[i]*b[i]<=x)
	{
       if(x%b[i]==0)
		   return 0;
	   i++;
	}
	return true;
}
//判定素数，概率方法
bool passTest(long n)
{
	long l ,m,b,i,k;
	m=n-1;
	l=0;
	while(m%2==0)
	{
		l++;
	    m/=2;
	} 
    b=rand()%n+1;
	if(modexp(b,m,n)==1) return 1;
    k=m;
	for(i=0; i<l; i++)
	{
		if(modexp(b,k,n)==n-1) return 1;
		k*=2;
	}
	return 0;
}
int main()
{
	long x, y,a,b,n;
	long d[10000]={2,3,2};
	long m[10000]={3,5,7};
	while(1)
	{
		cin>>a>>b>>x>>y;
		cout<<gcd(a,b)<<"  "<<lcm(x,y)<<endl;
        cin>>a>>b>>n;
        cout<<modexp(a,b,n)<<endl;
		cin>>a>>b;
		cout<<exEuclid(a,b,x,y)<<"  ";
		cout<<x<<"  "<<y<<endl;
		cin>>a>>b>>n;
        cout<<modu(a,b,n)<<endl;
        cout<<solmodu(3,d,m)<<endl;
		long k;
		searchprime(d,k);
		cin>>a;
		cout<<isPrime(a,d);
		while(1)
		{
			long w;
			cin>>w;
			cout<<passTest(w)<<endl;
		}
	}
	return 0;
}