注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zorksylar

Nothing is impossible , if distributed.

 
 
 

日志

 
 

数论_1  

2011-07-24 20:55:10|  分类: ACM_数论 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
注:参考了北大暑期课程ACM的课件,膜拜 林舒 大牛 Orz

补充知识:
mod的性质:
1)自反:a == a(mod m)
2)对称: a == b(mod m) <=> b == a(mod m)
3)传递: a == b(mod m) ,b == c(mod m) => a == c(mod m)
4)线性运算:
若: a == b(mod m), c == d(mod m) 
则: a ± c == b ± d(mod m)
     a*c == b*d(mod m)
5)除法:
ac ≡ bc (mod m) c!=0 则 a≡ b (mod m/gcd(c,m)) 其中gcd(c,m)表示c,m的最大公约数
特殊的:如果gcd(c,m) = 1,即c,m互质,那么a==b(mod m)
6)乘方
 如果a ≡ b (mod m),那么a^n ≡ b^n (mod m)
7)若a ≡ b (mod m),n|m,则 a ≡ b (mod n)
8)a ≡ b (mod mi) i=1,2...n 则 a ≡ b (mod [m1,m2,...mn]) 其中[m1,m2,...mn]表示m1,m2,...mn的最小公倍数
9)欧拉定理
若a和m互质,则aφ(m)≡1(mod m)
其中φ(m)为欧拉函数
10)费马小定理:
设a,p为正整数,且p为素数,那么a^(p-1) = 1(mod p),即a^p = a(mod p)
11)中国剩余定理


1.整除的性质:a=kb±c => a,b的公因数与b,c的公因数完全相同。
证明:利用性质3(a|b,a|c => a|kb±lc)证明:对于任意的a,b的公因数d,a=kb±c => c=±(a-kb) => d|c
公因数一定可以被这两个数整除!

假设用f(x, y)表示x,y的最大公约数,取k = x/y,b = x%y,则x = ky + b,如果一个数能够同时整除x和y,则必能同时整除b和y;而能够同时整除b和y的数也必能同时整除x和y,即x和y的公约数与b和y的公约数是相同的,其最大公约数也是相同的,则有f(x, y)= f(y, x%y)(y > 0)

2.最大公约数,最小公倍数
gcd(a,b)=gcd(b, a mod b)
gcd(a,b)=gcd(b, a-b)
lcm(a,b)=a*b/gcd(a,b)

1)欧几里德算法:
非递归:
int gcd(int a,int b)
{
int c;
if(a == 0) return b;
while(b != 0)
{
c = b,b = a%b, a = c;
}
return a;
}


递归:
int gcd(int a,int b)
{
if(a == 0) return b;
else return b==0?a:gcd(b,a%b);
}

时间复杂度:O(lgn)(最坏情况:斐波那契数列相邻的两项),空间复杂度:O(1),但是,对于大整数来说,取模运算非常耗时

2)Stein算法
渐近时间,空间复杂度均与欧几里德算法相同,
原理:gcd(ka,kb) = k*gcd(a,b)
最大特点:只有移位和加减法计算,避免了大整数的取模运算
unsigned MaxDivisor(unsigned a, unsigned b) 
    unsigned c = 0; 
    while(1)
    { 
    // 退出条件 
        if(a==0) 
            return b << c;
        else if(b == 0) 
            return a << c;
    // 为提高速度,避免用取模判断奇偶 
        if(!(a & 1) && !(b & 1)) //a,b 都是偶数 
        { 
            a >>= 1; b >>= 1; ++c; 
        } 
        else if(!(a & 1) && (b & 1)) //a偶 b奇 
        { 
            a >>= 1; 
        } 
        else if((a & 1) && !(b & 1)) //a奇 b偶 
        {
             b >>= 1; 
        } 
        else if((a & 1) && (b & 1)) //a,b都是奇数 
        { 
            unsigned tmp = a>b?b:a; //取较小的一个 
            a = a>b?a-b:(b-a); //绝对差值
            b = tmp; 
        } 
    }


3.扩展欧几里德算法(主要用于求解模线性方程)
扩展欧几里德定理:对于不完全为0的非负整数a,b,存在整数x,y使得gcd(a,b) = ax+by  (注:这里a,b,非负,x,y则可以是整数,负数,0)
用扩展欧几里德算法可以求出其中的x,y
扩展欧几里德算法:
返回:d = gcd(a,b) ,x,y为等式 ax+by = d 中的x,y
long extend_gcd(long a,long b,long *x,long *y)
{
long t,m;
if((b == 0) && (a == 0)) return -1;//表示无最大公因数
if(b == 0)
{
*x = 1; *y = 0;
return a;
else
{
m = extend_gcd(b, a%b ,x, y);
t = *x; 
*x = *y ;
*y = t - (a/b) *(*y);//回溯
}
return m;
}

整系数一次不定方程mx+ny = c的一般解为x,y算法如下:
1)设d = gcd(m,n) ,记
m = a*d   
n = b*d, 
 则  gcd(a,b) = 1,且整系数  mx + ny = d有整数解x0,y0,
即mx0 + ny0 = d(也就是说 x0,y0是ax+by = 1的整数解)
若d不是c的因子,则方程无整数解
若d是c的因子,
c = g*d
则方程mx+ny = c的一般解为
x = gx0 + bt;
y = gy0 - at;
t为任何整数



模线性方程(一次同余方程)求解:
ax = b(mod m) 其中,a,b,m已知,m > 0,求x的值
分析:
1)ax = b(mod m) <=> ax = ym + b <=> ax + my = b,求x,
2)方程有解,当且仅当 d = gcd(a,m),d能够整除b
3)令
a *  x0   + m *  y0   =  d ; *b/d后 =>
a * (x0*b/d) + m * (y0*b/d) = b;
故,ax + my = b的一个特解为:
x = x0*b/d;
y = y0*b/d;
故ax = b(mod m)的解(d个):
x = (x0  *  b / d + i * m / d)  mod m, i = 0,1,2,...,d-1
最小解为:

x  = (x0 * ( b / d) mod m  + m  ) mod( m / d )


练习题:
Poj 1061   根据题目条件写出方程,经过变换后,用扩展欧几里得算法求解

4.中国剩余定理(模线性方程组问题)(注:有时候,若方程组比较特殊,可以运用mod的运算规则,转换为一个模线性方程,用扩展欧几里得算法求解)
中国剩余定理:
设:m1,m2...,mn 是两两互素的n个正整数(注是两两互素正整数),
m = m1 * m2 * m3 * ... * mn ,Mi = m/mi, ( 1<= i <= n)
因为m1,m2,...mn互素,故 m 就是 mi  的最小公倍数
那么,模线性方程组x == bi(mod mi) (1 <= i <= n),的解为
x0 = ( (b1 * M1 * y1) + (b2 * M2 * y2) + ... + (bn * Mn * yn) ) mod m;
其中, yi 是 Mi * yi == 1(mod mi)的解

求解方法:
1)记m = m1 * m2 * m3 * ... * mn ,Mi = m/mi, ( 1<= i <= n)
对1 <= i <= n,求解Mi * yi = 1(mod mi),取其中的一个解,记yi
2)记x0 =  (b1 * M1 * y1) + (b2 * M2 * y2) + ... + (bn * Mn * yn) ;
则 x = x0(mod m)


代码:

long china(int m0[],int b[])
{
long m,x,y;
int i,n;
m = 1;
long a = 0;
for(i = 1;i <= n;i ++)
m *= m0[i];
for(i = 1;i <= n;i ++)
{
MM = m / m0[i];
extend_gcd(MM,m0[i],&x,&y);
a = (a + b[i] * MM * x ) % m;
}

return a;
}


对于同余方程组:

x=a1 (mod m1);   1

x=a2 (mod m2);    2

方程组有一个小于m(m1,m2的最小公倍数)的非负整数解的充分必要条件是(a1-a2)%(m1,m2)==0 ,同样利用扩展欧几里德算法。

两式联立:a1+m1*y=a2+m2*z。

则:a1-a2=m2*z-m1*y; 这样就可以了解出z和y,则:x=a2+m2*z;  

现在我们将其推广到一般情形:(设m1,m2,···,mk两两互素)

x=a1(mod m1);

x=a2(mod m2);

···

x=ak(mod mk);其在M=m1*m2*···*mk;中有唯一整数解。

记Mi=M/mi;因为gcd(Mi,mi)=1,故有两整数pi,qi满足Mi*pi+mi*qi=1,

如果记ei=Mi*pi;那么:ei=0 (mod mj)  ,j!=i;   ei=1(mod mj),j=i;

很明显,e1*a1+e2*a2+···+ek*ak就是方程的一个解,加减M倍后就可以得到最小非负整数解了。

如果m1,m2,···,mk不互素,那只能两个两个求了。

x=a1 (mod m1);  

x=a2 (mod m2);   

解完后,a=x; m=m1和m2的最小公倍数。即可。


练习:Poj 2891 


关于这个方法的证明,参考以下内容http://hi.baidu.com/buaa_babt/blog/item/63b6f6e95c6326fbcf1b3e03.html


先拿前两个方程, m ≡ r1 (mod) a1      m ≡ r2 (mod) a2

两式等同于 m = a1*x1 + r1  m = a2*x2 + r2

前式代入后式,消去m可得 a1*x1 = a2*x2 + r2 - r1

写成模方程,去一个未知数x2, a1*x1  ≡  r2 - r1 (mod) a2 ————@

扩展GCD可判定是否有解,若此方程无解,则后面所有方程都无需判定。

若有解,则能求出所有的解,然后代回方程 m = a1*x1 + r1得到每个可能的 m。 但是

在此,求出所有的解然后向下面每个方程测试显然有些不现实

而能得到的最小解以及这一解系的关系应当能写成相同模方程的形式。

看了很多份解题报告也没理解这个解系的方程是怎么写出来的

每一份解题报告写到这里都只有一句显然就给带过了。

反正我是个弱菜,我是没看出来它是怎么显然的。

@式的最小解x,解系x1 = x + i*(a2 / d)  (d = gcd(a1,a2)  , i = 0~d - 1)  这一点是已知的,在扩展GCD中可求的

然后把x 求出来,得到方程  m  ≡  a1 * x + r1 (mod) ( lcm (a1, a2))

-------------------------

早上爬起来开始翻初等数论书,终于明白差不多了。。T_T

某一句话是这样说的 对方程  ax  ≡  b (mod) n

d = gcd(a,n) 若 d | b 则 有 d 个解 ,最小的解为x0 = (x*(b/d) mod n + n )mod(n/d)

则所有满足方程 x = x0 (mod) (n/d) 的 x 都是原方程的解。

-------------------------

所以在@中求得最小解x后,可知这个方程的所有解可用方程 x1 = x (mod) (a2 / gcd(a1,a2)) 表示

代回m = a1*x1 + r1,得  m = a1 * (x (mod) (a2 / gcd(a1,a2)) ) + r1

移项 (m - r1) / a1 = x % (a2 / gcd(a1,a2)),等同于存在整数 y

y*(a2/ gcd(a1,a2)) + (m - r1)/a1 = x 两边乘 a1有

y * (  a1* a2 /gcd(a1,a2)) + (m - r1) = x*a1

y * (lcm(a1,a2)) + m = x*a1 + r1

写成方程消y,m   ≡   x*a1 + r1 mod (lcm(a1,a2))

 

至此,前两个方程合并为一个方程,取第三个方程与此方程按相同方法联解,至最终只剩一个方程即可。


  评论这张
 
阅读(453)| 评论(2)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018