算法篇————快速幂 - th是个小屁�?/title> <link rel="shortcut icon" href="/blog/favicon.ico">  <link rel="stylesheet" href="//cdn.bootcss.com/font-awesome/4.5.0/css/font-awesome.min.css"> <link rel="stylesheet" href="/blog/css/thplayer.css">  <link rel="stylesheet" href="/blog/css/style.css"> <script src="js/jquery.js"></script> </head> <body>  <header class="site-header"> <div class="header-inside"> <div class="logo"> <a href="http://www.tianhao.site" rel="home"> <img src="img/timg.jpg" alt="th是个小屁�? height="60"> </a> </div> <a class="header-name" href="/blog/"> <span>th是个小屁�?/span> 的部落宅 </a>  <nav class="navbar">  <div class="collapse"> <ul class="navbar-nav"> <li> <a href="/blog/."> <i class="fa fa-home "></i> 首页 </a> </li> <li> <a href="/blog/archives"> <i class="fa fa-archive "></i> 归档 </a> </li> <li> <a href="/blog/about"> <i class="fa fa-user "></i> 关于 </a> </li> <li> <a href="/blog/project"> <i class="fa fa-folder-open "></i> 项目 </a> </li> <li> <a href="/blog/photo"> <i class="fa fa-photo "></i> 相册 </a> </li> <li> <a href="/blog/guestbook"> <i class="fa fa-edit "></i> 留言 </a> </li> <li> <a href="/blog/one"> <i class="fa fa-bicycle "></i> one </a> </li> <li> <a href="/blog/atom.xml"> <i class="fa fa-send "></i> RSS </a> </li> </ul> </div>  </nav> <div class="button-wrap"> <button class="menu-toggle">Primary Menu</button> </div> </div> </header>  <div class="content-area"> <div class="post">  <div class="container"> <article>  <div class="post-header"> <h1 class="entry-title"> 算法篇————快速幂 </h1> </div> 　　　　　　　　<p class="a-posted-on">2016-09-15</p>  <div class="entry-content"> <p>今天介绍第二种算法，快速幂的使用，这个极大的方便了数值较大的数的之间的运算�?/p> <h2 id="快速幂取模"><a href="#快速幂取模" class="headerlink" title="快速幂取模"></a>快速幂取模</h2><p>假如我们要求a^b，而b是一个非常大的数的话，我们就可以用到快速幂的算法。这样复杂度不高，不会超时�?/p> <p>假如�?a ^ n 次方</p> <p>我们可以�?n 表示�?2^k1 + 2^k2 + 2^k3�?，可以证明所有数都可以用前式来表示。（其实就是二进制表示数的原理）<br><a id="more"></a><br>那么 a^n = a^2^k1 <em> a^2^k2 </em> a^2^k3…�?/p> <p>那么就可以利用二进制来加快计算速度了�?/p> <p>假如 a^22 , 22转化为二进制�?10110�?�?a^22 = a^16 <em> a^4 </em> a^2;</p> <p>那么是不是可以在O（logn）的复杂度求解�?/p> <p>下面是代码实现：（特别注意避免大数超出范围，用long long 存中间值）</p> <figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div></pre></td><td class="code"><pre><div class="line">typedef long long LL;</div><div class="line">LL fun(LL x,LL n,)</div><div class="line">{</div><div class="line"> LL res=1;</div><div class="line"> while(n>0)</div><div class="line"> {</div><div class="line"> if(n & 1)</div><div class="line"> res=(res*x)%Max;</div><div class="line"> x=(x*x)%Max;</div><div class="line"> n >>= 1;</div><div class="line"> }</div><div class="line"> return res;</div><div class="line">}</div></pre></td></tr></table></figure> <h2 id="矩阵快速幂"><a href="#矩阵快速幂" class="headerlink" title="矩阵快速幂"></a>矩阵快速幂</h2><p>前面是数与数之间的幂运算，对于矩阵与矩阵的幂运算，也可以用到快速幂的解决办法�?/p> <figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div><div class="line">51</div><div class="line">52</div><div class="line">53</div><div class="line">54</div><div class="line">55</div><div class="line">56</div><div class="line">57</div><div class="line">58</div><div class="line">59</div><div class="line">60</div><div class="line">61</div><div class="line">62</div><div class="line">63</div><div class="line">64</div><div class="line">65</div><div class="line">66</div><div class="line">67</div><div class="line">68</div><div class="line">69</div><div class="line">70</div><div class="line">71</div><div class="line">72</div></pre></td><td class="code"><pre><div class="line">/*===================================*/</div><div class="line">|| 快速幂（quickpow）模�?</div><div class="line">|| P 为等比，I 为单位矩�?/div><div class="line">|| MAX 要初始化！！！！</div><div class="line">||</div><div class="line">/*===================================*/</div><div class="line">/*****************************************************/</div><div class="line">#include <cstdio></div><div class="line">const int MAX = 3;</div><div class="line"></div><div class="line">typedef struct{</div><div class="line"> int m[MAX][MAX];</div><div class="line">} Matrix;</div><div class="line"></div><div class="line">Matrix P = {5,-7,4,</div><div class="line"> 1,0,0,</div><div class="line"> 0,1,0,</div><div class="line"> };</div><div class="line"></div><div class="line">Matrix I = {1,0,0,</div><div class="line"> 0,1,0,</div><div class="line"> 0,0,1,</div><div class="line"> };</div><div class="line"> </div><div class="line">Matrix matrixmul(Matrix a,Matrix b) //矩阵乘法</div><div class="line">{</div><div class="line"> int i,j,k;</div><div class="line"> Matrix c;</div><div class="line"> for (i = 0 ; i < MAX; i++)</div><div class="line"> for (j = 0; j < MAX;j++)</div><div class="line"> {</div><div class="line"> c.m[i][j] = 0;</div><div class="line"> for (k = 0; k < MAX; k++)</div><div class="line"> c.m[i][j] += (a.m[i][k] * b.m[k][j])%9997;</div><div class="line"> c.m[i][j] %= 9997;</div><div class="line"> }</div><div class="line"> return c;</div><div class="line">}</div><div class="line"> </div><div class="line">Matrix quickpow(long long n)</div><div class="line">{</div><div class="line"> Matrix m = P, b = I;</div><div class="line"> while (n >= 1)</div><div class="line"> {</div><div class="line"> if (n & 1)</div><div class="line"> b = matrixmul(b,m);</div><div class="line"> n = n >> 1;</div><div class="line"> m = matrixmul(m,m);</div><div class="line"> }</div><div class="line"> return b;</div><div class="line">}</div><div class="line"> /*************************************/</div><div class="line"></div><div class="line">int main()</div><div class="line">{</div><div class="line"> Matrix re;</div><div class="line"> int f[3] = {2,6,19};</div><div class="line"> long long n;</div><div class="line"> while (scanf("%I64d",&n) && n != 0)</div><div class="line"> {</div><div class="line"> if (n == 1)</div><div class="line"> printf("1\n");</div><div class="line"> else if (n <= 4)</div><div class="line"> printf("%d\n",f[n-2]);</div><div class="line"> else {</div><div class="line"> re = quickpow(n - 4);</div><div class="line"> printf("%d\n",(((re.m[0][0]*f[2]) </div><div class="line"> + (re.m[0][1]*f[1]) + (re.m[0][2]*f[0])) %9997 + 9997) % 9997);</div><div class="line"> }</div><div class="line"> }</div><div class="line"> return 0;</div><div class="line">}</div></pre></td></tr></table></figure> </div> </article> </div>  <div class="container" > <ul class="pager"> <li class="previous"> <a href="/blog/2016/09/14/算法篇——入门级算法/" rel="prev">下一�?/a> </li> <li class="next"> <a href="/blog/2016/09/17/《釜山行�?" rel="prev">上一�?/a> </li> </ul> </div> 　　　　 <div id="cloud-tie-wrapper" class="cloud-tie-wrapper"></div> <script src="https://img1.cache.netease.com/f2e/tie/yun/sdk/loader.js"></script> <script> var cloudTieConfig = { url: document.location.href, sourceId: "", productKey: "df8ef703a5a1404fb862cb96bfb8272c", target: "cloud-tie-wrapper" }; var yunManualLoad = true; Tie.loader("aHR0cHM6Ly9hcGkuZ2VudGllLjE2My5jb20vcGMvbGl2ZXNjcmlwdC5odG1s", true); </script> 　　　　 </div> </div> 　　 <div id="rocket-to-top"> <div class="level-2"></div> <div class="level-3"></div> </div> <script src="js/top.js"></script> <script type="text/javascript" src="js/jquery.js"></script>   <footer class="site-info"> <p> <span>th是个小屁�?© 2017</span> <span class="split">|</span> <span>th是个小屁孩的技术小�?/span> </p> <script async src="//dn-lbstatics.qbox.me/busuanzi/2.3/busuanzi.pure.mini.js"></script> 本站总访问量<span id="busuanzi_value_site_pv"></span>�? 本站访客�?span id="busuanzi_value_site_uv"></span>人次 </footer>   <script src="/blog/js/app.js"></script>  <script type="text/javascript"> var duoshuoQuery = {short_name:'th720309'}; (function() { var ds = document.createElement('script'); ds.type = 'text/javascript';ds.async = true; ds.src = (document.location.protocol == 'https:' ? 'https:' : 'http:') + '//static.duoshuo.com/embed.js'; ds.charset = 'UTF-8'; (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(ds); })(); </script>  </body> </html>