快速冪演算法
㈠ 不理解矩陣快速冪如何用於求斐波那契數列第n項%m的余數，望大神講解，越詳細越好
按照正常的邏輯是只要求a[2][2]={1,1,1,0}這個矩陣的n次方就可以得到斐波那契數列的第n項（即a[0][1]）的值。但是你忽略了一點，就是你在求a[0][1]，a[1][0]，a[1][1]的值的時候你的a[0][0]的值其實已經改變了，導致你求得的a[0][1]的值不正確，繼而影響到a[1][0]和a[1][1]的值。
因此，我們在遍歷這四個值的時候是不能改變其中任何一個的，只有改完之後才能去改變它的值。所以我們可以用幾個變數先將求得的新矩陣各值存起來，如下：
#include<stdio.h>
inta[2][2]={1,1,1,0},b[2][2]={1,1,1,0};//使用兩個二維數組表示快速冪演算法要用到的矩陣
intmain()
{
intn,m,i,j,t,u;
inta1,a2,a3,a4;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(m==-1&&n==-1)//當輸入的m.n值為-1時結束整個演算法
return0;
/*以下是對於第n項斐波那契數的計算*/
if(n==0)
a[0][0]=0;
elseif(n==1||n==2)
a[0][0]=1;
else
{
for(i=3;i<=n;i++)
{
a1=a[0][0]*b[0][0]+a[0][1]*b[1][0];
a2=a[0][0]*b[0][1]+a[0][1]*b[1][1];
a3=a[1][0]*b[0][0]+a[1][1]*b[1][0];
a4=a[1][0]*b[0][1]+a[1][1]*b[1][1];
a[0][0]=a1;
a[0][1]=a2;
a[1][0]=a3;
a[1][1]=a4;
}
}
t=a[0][0];
a[0][0]=1;//重置矩陣
a[0][1]=1;
a[1][0]=1;
a[1][1]=0;
if(m==0)
a[0][0]=0;
elseif(m==1||m==2)
a[0][0]=1;
else
{
for(j=3;j<=m;j++)
{
a1=a[0][0]*b[0][0]+a[0][1]*b[1][0];
a2=a[0][0]*b[0][1]+a[0][1]*b[1][1];
a3=a[1][0]*b[0][0]+a[1][1]*b[1][0];
a4=a[1][0]*b[0][1]+a[1][1]*b[1][1];
a[0][0]=a1;
a[0][1]=a2;
a[1][0]=a3;
a[1][1]=a4;
}
}
u=a[0][0];
a[0][0]=1;//重置矩陣
a[0][1]=1;
a[1][0]=1;
a[1][1]=0;
t=t%u;
printf("%d ",t);
}
return0;
}
還有一點，就是你的矩陣相乘後兩項寫錯了，自己對比一下改過來吧。
這樣就能得到你想要的結果了。
㈡ 求快速冪演算法c語言實現程序
㈢ 次方的快速演算法
次方有兩種快速演算法：
第一種是直接用乘法計算，例：3⁴=3×3×3×3=81。
第二種則是用次方階級下的數相乘，例：3⁴=9×9=81
次方最基本的定義是：設a為某數，n為正整數，a的n次方表示為aⁿ，表示n個a連乘所得之結果，如2⁴=2×2×2×2=16。次方的定義還可以擴展到0次方和負數次方等等。
負數次方
由5的0次方繼續除以5就可以得出5的負數次方。
例如： 5的0次方是1 （任何非零數的0次方都等於1。)
5的-1次方是0.2 1÷ 5 =0.2
5的-2次方是0.04 0.2÷5 =0.04
因為5的-1次方是0.2 ，所以5的-2次方也可以表示為0.2×0.2=0.04
5的-3次方則是0.2×0.2×0.2=0.008
由此可見，一個非零數的-n次方=這個數的倒數的n次方。
(3)快速冪演算法擴展閱讀：
0的次方
0的任何正數次方都是0，例：0⁵=0×0×0×0×0=0
0的0次方無意義。
一個數的0次方
任何非零數的0次方都等於1。原因如下：
通常代表3次方
5的3次方是125，即5×5×5=125
5的2次方是25，即5×5=25
5的1次方是5，即5×1=5
由此可見，n≧0時，將5的（n+1）次方變為5的n次方需除以一個5，所以可定義5的0次方為：
5 ÷ 5 = 1。
㈣ 快速冪演算法原理
快速冪
顧名思義，快速冪就是快速算底數的n次冪。其時間復雜度為 O(log2N)， 與樸素的O(N)相比效率有了極大的提高。
中文名
快速冪
外文名
Fast Power
時間復雜度
log(n)
性質
快速算底數的n次冪
快速
導航
實現
代碼比較
原理
快速冪演算法的核心思想就是每一步都把指數分成兩半，而相應的底數做平方運算。這樣不僅能把非常大的指數給不斷變小，所需要執行的循環次數也變小，而最後表示的結果卻一直不會變。
讓我們先來看一個簡單的例子：
3^10=3*3*3*3*3*3*3*3*3*3
3^10=(3*3)*(3*3)*(3*3)*(3*3)*(3*3)
3^10=(3*3)^5
3^10=9^5
9^5=（9^4）*（9^1）
9^5=（9^4）*（9^1）
9^5=（6561^1）*(9^1)
以下以求a的b次方來介紹[1]
把b轉換成二進制數。
該二進制數第i位的權為
例如
11的二進制是1011
因此，我們將a11轉化為算
實現
快速冪可以用位運算來實現
b and 1{也就是取b的二進制最低位(即第0位)判斷b是否為奇數，是則為1}
b shr 1{就是去掉b的二進制最低位(即第0位)}
C++實現為
b & 1//取b二進制的最低位，判斷和1是否相同，相同返回1，否則返回0，可用於判斷奇偶
b>>1//把b的二進制右移一位，即去掉其二進制位的最低位
以下為pascal的實現：
var a,b,n:int64;
function f(a,b,n:int64):int64;
var t,y:int64;
begin
t:=1; y:=a;
while b<>0 do begin
if(b and 1)=1 then t:=t*y mod n;
y:=y*y mod n;{這里用了一個技巧,y*y即求出了a^(2^(i-1))不知道這是什麼的看原理
a^(2^(i-1))*a^(2^(i-1))=a^(2^i)
而且一般情況下a*b mod c =(a mod c)*(b mod c) mod c}
b:=b shr 1;{去掉已經處理過的一位}
end;
exit(t);
end;
begin
read(a,b,n);{n是模}
writeln(f(a,b,n));
end.
[1]
以下為C的實現，為了方便與pascal的對照，變數全部與上面相同.可以對照查看。
遞歸版：[2]
ll pow(ll a,ll i){
if (i==0) return 1;
int temp=pow(a,i>>1);
temp=temp*temp%MOD;
if (i&1) temp=(ll)temp*a%MOD;
return temp%MOD;
}
非遞歸版：
ll f(ll a,ll b,ll n){
int t,y;
t=1; y=a;
while (b!=0){
if (b&1==1) t=t*y%n;
y=y*y%n; b=b>>1;
}
return t;
}
㈤ c語言快速冪代碼
int pow( int a, int b )
{
int r = 1, base = a;
while( b != 0 )
{
if( b & 1 )
r *= base;
base *= base;
b >>= 1;
}
return r;
}
㈥ c語言，快速冪代碼是什麼，怎麼用
所謂的快速冪，實際上是快速冪取模的縮寫，簡單的說，就是快速的求一個冪式的模(余)。在程序設計過程中，經常要去求一些大數對於某個數的余數，為了得到更快、計算范圍更大的演算法，產生了快速冪取模演算法。
用遞歸
x^y可如下實現
unsigned long pow(int x, unsigned y)
{
unsigned long tmp;
if(!y) return 1;
tmp = pow(x, y / 2);
if(y % 2 == 0) return (tmp * tmp);
else return (tmp * tmp * x);
}
㈦ 在快速冪運算演算法中，為啥把n&1換成n==1就會出錯呢
對於 表達式「n&1」表示的是n與1的按位與（其業務邏輯應該是：當且僅當n為奇數時結果為1，其餘時候為0，不過我也有段時間不用c++了，可能記錯）
對於表達式」n==1「表示的是判斷兩整數是否相等（其業務邏輯是：當且僅當n為1時結果為true其餘時候為false）
這兩個業務邏輯不同，結果自然不同
㈧ 如何計算快速冪，比如 x^100000000次方，直接循環很慢。。謝謝了
因為 x^n = (x^(n/2))^2
根據這個公式，可以在 log2N時間內算出乘法冪
遞歸演算法：
int pow(int x,int n)
{
if(n==1) return x;
else if(n&1) //n is odd
{
return x*pow(x,n/2);
}
else
{
return pow(x,n/2);
}
}
非遞歸演算法:
int pow(int x,int n)
{
int temp(x),res(1);
while(n)
{
if(n&1)
{
res *= temp;
}
temp *= temp;
n>>=1;
}
return res;
}