数论——欧几里得与模线性方程

2019-04-13 17:24发布

站内文章 / 模拟电子
11395 0 1610
欧几里得定理     对任意的非负整数a和和任意正整数b，有gcd(a, b) = gcd(b, a%b)     这个定理可以用来求a和b的最大公约数，假设a>b，时间复杂度为O(logb)。 扩展欧几里得     它是欧几里得算法的推广，使它能计算出满足下列条件的整数系数x和y： ax + by = gcd(a, b)     注意，x和y可能为0或负数，用它来计算模乘法的逆元也很有效。     根据gcd(a,b)=gcd(b,a%b)                                               ax + by = d                                        (1)     bx' + (a%b)y' = d  -->  bx' + (a-a/b*b)y' =  d -->                                ay' + b(x' - a/b*y') = d                                     (2)     若求出x'和y'，比较式(1)和式(2)的系数，有： x = y',  y = x' - a/b*y'     扩展欧几里得与欧几里得运行时间相同，两者相差不超过一个常数因子。 typedef __int64 int64; /** 功能：已知a,b，求解ax+by = gcd(a,b) 输入参数：a和b 输出参数：返回gcd(a,b)，x，y。 */ int64 Extend_Euclid(int64 a, int64 b, int64& x, int64& y) { if(b == 0) { x = 1; y = 0; return a; } int64 d = Extend_Euclid(b,a%b,x,y); int64 t = x; x = y; y = t - a/b*y; return d; } 求解模线性方程     考虑求解下列方程： ax = b (mod n)     设表示由a生成的Zn的子群。由于={ax mod n, x>0}，所有方程有一个解b当且仅当b属于。 定理：   对任意正整数a和n，如果d=gcd(a,n)，则在Zn中 = = {0,d,2d,...,((n/d)-1)d} 因此有|| = n/d。       方程ax=b(mod n)对于未知量x有解，当且仅当gcd(a,b)|b。它或者误解，或者有d个解，周期为n/d。 将方程改写为ax + ny = b。可以先求ax'+ny'=gcd(a,n)=d的一组解x'y'，则x'b/gcd(a,b)是原方程的一个解，令它为x0。 解集可以写为： xi = x0 + (n/d)*i 证明： axi mod n = a(x0+(n/d)*i) mod n = (ax0 + ina/d) mod n = ax0 mod n (因为d|a) = b 所以方程有d个不同的解。 /** 功能：求解模线性方程ax=b(mod n) 输入参数：a,b,n 返回参数：模线性方程解的最小值，无解返回-1 */ int64 Modular_Linear_Equation(int64 a, int64 b, int64 n) { int64 x,y; int64 d = Extend_Euclid(a,n,x,y); if(b%d) return -1; int64 x0 = x*(b/d); x0 = (x0%n+n)%n; return x0%(n/d); //d个解,相差n/d (模n/d同余) } 例：POJ1061 2115    附POJ1061代码 #include #include #include using namespace std; typedef __int64 int64; int64 Extend_Euclid(int64 a, int64 b, int64& x, int64& y) { if(b==0) { x=1,y=0; return a; } int64 d = Extend_Euclid(b,a%b,x,y); int64 t = x; x = y; y = t - a/b*y; return d; } int64 Mod_Linear_Equation(int64 a, int64 b, int64 n) { int64 x1,y1,gcd; gcd = Extend_Euclid(a,n,x1,y1); if(b%gcd) return -1; //解集共d个解，周期为n/d，xi=x1+(n/d)*i(mod n) return (x1*b/gcd%n + n)%n%(n/gcd); } int main() { int64 m,n,x,y,L; int64 a,b,N; while(scanf("%I64d %I64d %I64d %I64d %I64d",&x,&y,&m,&n,&L)!=EOF) { a = m - n; b = y - x; N = L; if(a==0) { printf("0 "); continue; } if(a < 0) { a = -a; b = -b; } if(b < 0) b = (b%N+N)%N; int64 result = Mod_Linear_Equation(a,b,N); if(result == -1) printf("Impossible "); else printf("%I64d ",result); } return 0; }  

热门文章