快速幂，矩阵快速幂（模板）

左手的ㄟ右手 2022-06-11 03:57 312阅读 0赞

1，整数快速幂：

C++ Code

2，含有取余的整数快速幂：

C++ Code

<table style="font-family:Consolas, 'Courier New';font-size:12px;vertical-align:text-top;line-height:15px;"> 
 <tbody> 
 <tr> 
 <td style="color:#008284;background-color:#e3e3e3;vertical-align:text-top;"> 
 <div style="margin:7px;text-align:right;white-space:nowrap;">
 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 
 </div></td> 
 <td style="background-color:#008284;padding:1px;"> 
 <div style="border:1px #008284 solid;"></div></td> 
 <td style="background-color:#efefef;width:100%;vertical-align:text-top;color:#000000;"> 
 <div style="margin:7px;"> 
 #include&nbsp;&lt;iostream&gt; 
 
 using&nbsp; 
 namespace&nbsp;std; 
 
 
 int&nbsp;pw( 
 int&nbsp;x,&nbsp; 
 int&nbsp;y,&nbsp; 
 int&nbsp;p) 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 if&nbsp;(!y) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;res&nbsp;=&nbsp;pw((x&nbsp;*&nbsp;x)&nbsp;%&nbsp;p,&nbsp;y&nbsp;/&nbsp; 
 2,&nbsp;p); 
 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 if&nbsp;(y&nbsp;&amp;&nbsp; 
 1)&nbsp;&nbsp;&nbsp; 
 //判断奇偶性&nbsp;y&amp;1==1为奇数,反之为偶数 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res&nbsp;=&nbsp;res&nbsp;*&nbsp;x&nbsp;%&nbsp;p; 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp;res; 
 } 
 
 
 int&nbsp;main() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;x,&nbsp;y,&nbsp;p; 
 &nbsp;&nbsp;&nbsp;&nbsp;cin&nbsp;&gt;&gt;&nbsp;x&nbsp;&gt;&gt;&nbsp;y&nbsp;&gt;&gt;&nbsp;p; 
 &nbsp;&nbsp;&nbsp;&nbsp;cout&nbsp;&lt;&lt;&nbsp;pw(x,&nbsp;y,&nbsp;p)&nbsp;&lt;&lt;&nbsp;endl; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 0; 
 } 
 
 </div></td> 
 </tr> 
 </tbody> 
</table>

或者

C++ Code

3，矩阵快速幂：

C++ Code

<table style="width:100%;font-family:Consolas, 'Courier New';font-size:12px;vertical-align:text-top;line-height:15px;"> 
 <tbody> 
 <tr> 
 <td style="color:#008284;background-color:#e3e3e3;vertical-align:text-top;"> 
 <div style="margin:7px;text-align:right;white-space:nowrap;">
 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 
 35 
 36 
 37 
 38 
 39 
 40 
 41 
 42 
 43 
 44 
 45 
 46 
 47 
 48 
 49 
 50 
 51 
 52 
 53 
 54 
 55 
 56 
 57 
 58 
 59 
 60 
 61 
 62 
 63 
 64 
 65 
 66 
 67 
 68 
 69 
 70 
 71 
 72 
 73 
 74 
 75 
 76 
 77 
 78 
 79 
 80 
 
 </div></td> 
 <td style="background-color:#008284;padding:1px;"> 
 <div style="border:1px #008284 solid;"></div></td> 
 <td style="background-color:rgb(239,239,239);width:100%;vertical-align:text-top;"> 
 <div style="margin:7px;"> 
 #include&nbsp;&lt;cstdlib&gt; 
 
 #include&nbsp;&lt;cstring&gt; 
 
 #include&nbsp;&lt;cstdio&gt; 
 
 #include&nbsp;&lt;iostream&gt; 
 
 using&nbsp; 
 namespace&nbsp;std; 
 
 
 int&nbsp;N; 
 
 ///以3*3的矩阵为例 
 struct&nbsp;matrix 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;a[ 
 3][ 
 3]; 
 }&nbsp;origin,res; 
 
 
 matrix&nbsp;multiply(matrix&nbsp;x,matrix&nbsp;y) 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 ///矩阵乘法 &nbsp;&nbsp;&nbsp;&nbsp;matrix&nbsp;temp; 
 &nbsp;&nbsp;&nbsp;&nbsp;memset(temp.a, 
 0, 
 sizeof(temp.a)); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i= 
 0;&nbsp;i&lt; 
 3;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;j= 
 0;&nbsp;j&lt; 
 3;&nbsp;j++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;k= 
 0;&nbsp;k&lt; 
 3;&nbsp;k++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;temp.a[i][j]+=x.a[i][k]*y.a[k][j]; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp;temp; 
 } 
 
 
 void&nbsp;init() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 ///初始化，产生随机数 &nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "随机数组如下:\n"); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i= 
 0;&nbsp;i&lt; 
 3;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;j= 
 0;&nbsp;j&lt; 
 3;&nbsp;j++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;origin.a[i][j]=rand()% 
 10; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "%8d",origin.a[i][j]); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "\n"); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "\n"); 
 &nbsp;&nbsp;&nbsp;&nbsp;memset(res.a, 
 0, 
 sizeof(res.a)); 
 &nbsp;&nbsp;&nbsp;&nbsp;res.a[ 
 0][ 
 0]=res.a[ 
 1][ 
 1]=res.a[ 
 2][ 
 2]= 
 1;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///将res.a初始化为单位矩阵 } 
 
 
 void&nbsp;calc( 
 int&nbsp;n) 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 ///快速幂核心代码 &nbsp;&nbsp;&nbsp;&nbsp; 
 while(n) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(n&amp; 
 1) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res=multiply(res,origin); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;n&gt;&gt;= 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;origin=multiply(origin,origin); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "%d次幂结果如下：\n",n); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i= 
 0;&nbsp;i&lt; 
 3;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;j= 
 0;&nbsp;j&lt; 
 3;&nbsp;j++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "%8d",res.a[i][j]); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "\n"); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "\n"); 
 } 
 
 int&nbsp;main() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 ///主函数 &nbsp;&nbsp;&nbsp;&nbsp; 
 while(cin&gt;&gt;N) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;init(); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;calc(N); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 0; 
 } 
 
 </div></td> 
 </tr> 
 </tbody> 
</table>