好久没写题目了=。=手是越来越生了。。。
好吧这是一个模版,希望大家能用到。
/**** *@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; }