吉林省冬令营DAY4知识梳理与总结

DAY4讲的是数论基础，学到了很多东西，做一下便于自己理解的整理

• 　　快速幂

要求一个数 a^bmodP

考虑a^b,把b按二进制分解

例如：

         5⁹

       （9）₁₀=（1001） ₂ =1*2³+0*2²+0*2¹+1*2⁰

　　　那么我们可以把b的所有为1的二进制位对应的次幂相乘得到a^b

　　  5⁹= 5¹*5⁸

代码如下

 1 int pw(int a,int b)
 2 {
 3     int r=1;
 4     while(b)
 5     {
 6         if(b&1) r=r*a;
 7         a*=a;
 8         b>>=1;
 9     }
10     return r;

快速幂

 

• 　　线性同余方程

　 形如 a*x≡b(mod p)，求x的值

    一些性质：

                 1.如果gcd(a,p)=1,则方程有且仅有一个解 x=a^-1b

　　2.方程有解? gcd(??,??)|b，且解数为gcd(??,??)

   同余方程与不等式a*x=p*y+b同解

   例如:  51*x≡4(mod 50)

             x=(1/51)*4

            52*x≡4(mod12)

             x=gcd(52,12)  x=4 

• 　　扩展欧几里得算法

   ：在求出gcd(a,b)时还可已顺带解出不定方程 a*x+b*y=gcd(a,b)的一组解

　  此方程等价于同余方程a*x≡gcd(a,b)(mod b)

     x=gcd(a,b)

 　余下内容，再做整理

　　

吉林省冬令营DAY4知识梳理与总结

原文：http://www.cnblogs.com/zby-ccsygz/p/6284215.html