现在的位置: 首页 > 综合 > 正文

整除与剩余

2013年06月08日 ⁄ 综合 ⁄ 共 5575字 ⁄ 字号 评论关闭

好久没写题目了=。=手是越来越生了。。。

好吧这是一个模版,希望大家能用到。

/****
	*@Polo-shen
	*
	*/
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>

using namespace std;

#define DBG 0
#define ShowLine DBG && cout<<__LINE__<<">>| "
#define dout DBG && cout<<__LINE__<<">>| "
#define write(x) #x" = "<<(x)<<" "
#define awrite(array,num) #array"["<<num<<"]="<<array[num]<<" "

#ifndef min
#define min(x,y) ((x) < (y) ? (x) : (y))
#endif

#ifndef max
#define max(x,y) ((x) > (y) ? (x) : (y))
#endif

/*
*类名:NumberTheory_2
*具体实例:nt
*包括函数:
*	int64 gcd(int64 a,int64 b)
*		求最大公约数gcd(a,b)
*
*	int64 lcm(int64 a,int64 b)
*		求最小公倍数lcm(a,b)
*
*	int64 q_mul_mod(int64 a,int64 b,int64 m)
*		快速乘函数,用于计算a*b mod m
*
*	int64 q_pow_mod(int64 a,int64 b,int64 m)
*		快速幂函数,用于计算a^b mod m
*
*	int64 gcd_ex(int64 a,int64 b,int64& x,int64& y)
*		扩展欧几里得,得到gcd(a,b)=ax+by
*
*	int64 inverse(int64 n,int64 mod)
*		求n在模mod下的逆元
*
*	vector<int64> line_mod_equation(int64 a,int64 b,int64 n)
*		单变元模线性方程
*		已知a,b,n,求x,使得ax == b(mod n)
*
*	int64 CRT(int64 a[],int64 m[],int64 n)
*		中国剩余定理
*		求方程组x == ai(mod mi)(0 <= i < n)的解x
*
*	bool g_test(int64 g,int64 p)
*		原根测试函数,检查g^((p-1)/a) == 1(mod p) 是否成立
*		返回值为:1(是原根),0(不是原根)
*
*	int64 primitive_root(int64 p)
*		求mod p意义下的原根,p为素数
*
*	int64 modsqr(int64 a,int64 n)
*		平方剩余
*		给定a,n(n为质数),求x^2 == a(mod n)的最小整数解
*
*	int64 Legendre(int64 d,int64 p)
*		勒让德符号,计算(d|p)
*
*	int64 discrete_log(int x,int n,int m)
*		离散对数
*		给定x,n,m(m为质数),求x^y == n(mod m)的最小整数解
*
*	vector<int64> residue(int N,int a,int p)
*		N次剩余
*		给定N,a,p(p为质数),求x^N == a(mod p)在模p意义下的所有解
*/
class NumberTheory_2{
public:
	typedef long long int64;

	int64 gcd(int64 a,int64 b){
		return (b==0)?a:gcd(b,a%b);
	}

	int64 lcm(int64 a,int64 b){
		return a/gcd(a,b)*b;
	}

	int64 q_mul_mod(int64 a,int64 b,int64 m){
		a%=m;
		b%=m;
		int64 t=0;
		while (b){
			if (b&1){
				t+=a;
				if (t>=m)t-=m;
			}
			a<<=1;
			if (a>=m)a-=m;
			b>>=1;
		}
		return t;
	}

	int64 q_pow_mod(int64 a,int64 b,int64 m){
		int64 ans=1;
		a%=m;
		while (b){
			if (b&1){
				ans=q_mul_mod(ans,a,m);
				b--;
			}
			b/=2;
			a=q_mul_mod(a,a,m);
		}
		return ans;
	}

	int64 gcd_ex(int64 a,int64 b,int64& x,int64& y){
		if (b==0){
			x=1;
			y=0;
			return a;
		}
		int64 d=gcd_ex(b,a%b,x,y);
		int64 t=x;
		x=y;
		y=t-a/b*y;
		return d;
	}

	int64 inverse(int64 n,int64 mod){
		int64 x,y;
		int64 t=gcd_ex(n,mod,x,y);
		return (x%mod+mod)%mod;
	}

	vector<int64> line_mod_equation(int64 a,int64 b,int64 n){
		int64 x,y;
		int64 d=gcd_ex(a,n,x,y);
		vector<int64> ans;
		ans.clear();
		if (b%d==0){
			x%=n;x+=n;x%=n;
			ans.push_back(x/(b/d)%(n/d));
			for (int64 i=1;i<d;i++){
				ans.push_back((ans[0]+i*n/d)%n);
			}
		}
		return ans;
	}

	int64 CRT(int64 a[],int64 m[],int64 n){
		int64 M=1;
		for (int i=1;i<n;i++){
			M*=m[i];
		}
		int64 ret=0;
		for (int i=1;i<n;i++){
			int64 x,y;
			int64 tm=M/m[i];
			gcd_ex(tm,m[i],x,y);
			ret=(ret+tm*x*a[i])%M;
		}
		return (ret+M)%M;
	}

	vector<int64> a;

	bool g_test(int64 g,int64 p){
		for (int64 i=0;i<a.size();i++){
			if (q_pow_mod(g,(p-1ll)/a[i],p)==1ll){
				return 0;
			}
		}
		return 1;
	}

	int64 primitive_root(int64 p){
		int64 tmp=p-1;
		for (int64 i=2;i<=tmp/i;i++){
			if (tmp%i==0){
				a.push_back(i);
				while (tmp%i==0){
					tmp/=i;
				}
			}
		}
		if (tmp!=1){
			a.push_back(tmp);
		}
		int64 g=1;
		while (1){
			if (g_test(g,p)){
				return g;
			}
			g++;
		}
	}

	int64 modsqr(int64 a,int64 n){
		int64 b,k,i,x;a%=n;
		if (n==2)return a%n;
		if (q_pow_mod(a,(n-1)/2,n)==1){
			if (n%4==3){
				x=q_pow_mod(a,(n+1)/4,n);
			}
			else{
				for (b=1;q_pow_mod(b,(n-1)/2,n)==1;b++);
				i=(n-1)/2;
				k=0;
				do{
					i/=2;
					k/=2;
					if ((q_pow_mod(a,i,n)
						*(int64)q_pow_mod(b,k,n)+1)%n==0){
							k+=(n-1)/2;
					}
				}while (i%2==0);
				x=(q_pow_mod(a,(i+1)/2,n)
					*(int64)q_pow_mod(b,k/2,n))%n;
			}
			if (x*2>n){
				x=n-x;
			}
			return x;
		}
		return -1;
	}

	int64 Legendre(int64 d,int64 p){
		if (d>0){
			d%=p;
			if(d==0) return 0;
			if (q_pow_mod(d,(p-1)/2,p)==1){
				return 1;
			}
			else return -1;
		}
		else{
			int64 coef=((p-1)%4==0)?1:-1;
			d=-d;d%=p;
			if(d==0) return 0;
			if (q_pow_mod(d,(p-1)/2,p)==1){
				return coef;
			}
			else return -coef;
		}
	}

	int64 discrete_log(int64 x,int64 n,int64 m){
		map<int64,int>rec;
		int s=(int)(sqrt((double)m));
		for (;(int64)s*s<=m;){
			s++;
		}
		int64 cur=1;
		for (int i=0;i<s;i++){
			rec[cur]=i;
			cur=cur*x%m;
		}
		int64 mul=cur;
		cur=1;
		for (int i=0;i<s;i++){
			int64 more=(int64)n*q_pow_mod(cur,m-2,m)%m;
			if (rec.count(more)){
				return i*s+rec[more];
			}
			cur=cur*mul%m;
		}
		return -1;
	}

	vector<int64> residue(int64 N,int64 a,int64 p){
		int64 g=primitive_root(p);
		int64 m=discrete_log(g,a,p);
		vector<int64> ret;
		if (a==0){
			ret.push_back(0);
			return ret;
		}
		if (m==-1){
			return ret;
		}
		int64 A=N,B=p-1,C=m,x,y;
		int64 d=gcd_ex(A,B,x,y);
		if (C%d!=0){
			return ret;
		}
		x=x*(C/d)%B;
		int64 delta=B/d;
		for (int i=0;i<d;i++){
			x=((x+delta)%B+B)%B;
			ret.push_back((int64)q_pow_mod(g,x,p));
		}
		sort(ret.begin(),ret.end());
		ret.erase(unique(ret.begin(),ret.end()),ret.end());
		return ret;
	}

}nt;
int main(){
	cout<<"Running tests.\n"<<endl;

	cout<<"Test 1: gcd, lcm"<<endl;
	long long a=358,b=7497;
	cout<<write(a)<<write(b)<<endl;
	cout<<write(nt.gcd(a,b))<<endl;
	cout<<write(nt.lcm(a,b))<<endl;
	cout<<endl;

	cout<<"Test 2: q_mul_mod, q_pow_mod"<<endl;
	const long long module=10007;
	cout<<write(a)<<write(b)<<endl;
	cout<<write(nt.q_mul_mod(a,b,module))<<endl;
	cout<<write(nt.q_pow_mod(a,b,module))<<endl;
	cout<<endl;

	cout<<"Test 3: gcd_ex"<<endl;
	long long x=0,y=0;
	cout<<write(a)<<write(b)<<endl;
	cout<<write(nt.gcd_ex(a,b,x,y))<<endl;
	cout<<write(x)<<write(y)<<endl;
	cout<<"a*x+b*y="<<a<<" * "<<x<<" + ";
	cout<<b<<" * "<<y<<"\n      =";
	cout<<a*x<<" + "<<b*y<<endl;
	cout<<"      ="<<a*x+b*y<<endl;
	cout<<endl;

	cout<<"Test 4: inverse,line_mod_equation"<<endl;
	cout<<write(a)<<write(b)<<endl;
	cout<<write(nt.inverse(a,module))<<write(nt.inverse(b,module))<<endl;
	vector<long long> ans;
	ans=nt.line_mod_equation(a,b,module);
	for (vector<long long>::iterator it=ans.begin();it!=ans.end();it++){
		cout<<*it<<endl;
	}
	cout<<endl;

	cout<<"Test 5: CRT"<<endl;
	long long ai[3]={2,3,2},m[3]={3,5,7};
	cout<<write(nt.CRT(ai,m,3))<<endl;
	cout<<endl;

	cout<<"Test 6: Legendre, modsqr"<<endl;
	cout<<write(nt.Legendre(286,563))<<write(nt.Legendre(429,563))<<endl;
	cout<<write(nt.modsqr(286,563))<<write(nt.modsqr(429,563))<<endl;
	cout<<endl;

	cout<<"Test 7: discrete_log, residue"<<endl;
	cout<<write(nt.discrete_log(3,47,10007))<<endl;
	ans.clear();
	ans=nt.residue(5,47,10007);
	for (vector<long long>::iterator it=ans.begin();it!=ans.end();it++){
		cout<<*it<<endl;
	}
	cout<<endl;

	cout<<"Test ends."<<endl;

	return 0;
}

 

抱歉!评论已关闭.