五月天青色头像情侣网名,国产亚洲av片在线观看18女人,黑人巨茎大战俄罗斯美女,扒下她的小内裤打屁股

歡迎光臨散文網(wǎng) 會員登陸 & 注冊

【僅供測試】快速冪與龜速乘

2023-08-16 20:49 作者:Mount256  | 我要投稿

1. 快速冪2. 龜速乘3. 快速冪取模4. 龜速乘取模5. 快速冪取模優(yōu)化6. 矩陣乘7. 矩陣快速冪8. 矩陣快速冪用于遞推式斐波那契數(shù)列遞推式的一些套路參考資料

1. 快速冪

算法原理：

  • 計算：
  • 僅需計算 3 次，而非 11 次
  • 計算 ：
  • 僅需計算 3 次，而非 10 次

算法思路：

  • 若指數(shù)是偶數(shù)，則將底數(shù)平方，指數(shù)除以 2。
  • 若指數(shù)是奇數(shù)，則將底數(shù)平方，指數(shù)除以 2，再乘上底數(shù)。

算法代碼：

typedef?unsigned?long?long?uLL;

//?快速冪?a^b
uLL?power?(uLL?a,?uLL?b){
????uLL?r?=?1;
????while?(b?!=?0){
????????if?(b?&?1)??//?(b?%?2?==?1)
????????????r?=?r?*?a;
????????b?=?b?>>?1;?//?(b?=?b?/?2)
????????a?=?a?*?a;
????}
????return?r;
}

舉例：

  • 初始值：a = 3，b = 11
  • 第 1 輪：（11 % 2 == 1）r=1x3=3，b=5，a==9
  • 第 2 輪：（5 % 2 == 1）r=3x==27，b=2，a===81
  • 第 3 輪：（2 % 2 == 0）r 不變，b=1，a==
  • 第 4 輪：（1 % 2 == 1）r=x=，b=0，a==
  • 得到 r = =

2. 龜速乘

算法原理：將其中一個乘數(shù)分解成 2 的冪次相加。

算法代碼：

typedef?unsigned?long?long?uLL;

//?龜速乘?a*b
uLL?mul?(uLL?a,?uLL?b){
????uLL?r?=?0;
????while?(b?!=?0){
????????if?(b?&?1)??//?(b?%?2?==?1)
????????????r?=?r?+?a;
????????b?=?b?>>?1;?//?(b?=?b?/?2)
????????a?=?a?+?a;
????}
????return?r;
}

3. 快速冪取模

初等數(shù)論中有如下公式：

(a × b) % m = ((a % m) × (b % m)) % m

推廣：

(a × b × c...) % m = ((a % m) × (b % m) × (c % m) × ... ) % m

(a^b) % m = (a × a × a...) % m = ((a % m) × (a % m) × (a % m) × ... ) % m

算法代碼：

typedef?unsigned?long?long?uLL;

//?快速冪取模?(a^b)?%?p
uLL?powerMod?(uLL?a,?uLL?b,?uLL?p){
????uLL?r?=?1;
????while?(b?!=?0){
????????if?(b?&?1)??//?(b?%?2?==?1)
????????????r?=?(r?*?a)?%?p;
????????b?=?b?>>?1;?//?(b?=?b?/?2)
????????a?=?(a?*?a)?%?p;
????}
????return?r;
}

4. 龜速乘取模

算法原理：(a × b) % m = ((a % m) × (b % m)) % m

算法代碼：

//?龜速乘取模?(a*b)?%?p
uLL?mulMod?(uLL?a,?uLL?b,?uLL?p){
????uLL?r?=?0;
????while?(b?!=?0){
????????if?(b?&?1)??//?(b?%?2?==?1)
????????????r?=?(r?+?a)?%?p;
????????b?=?b?>>?1;?//?(b?=?b?/?2)
????????a?=?(a?+?a)?%?p;
????}
????return?r;
}

5. 快速冪取模優(yōu)化

算法原理：注意到快速冪取模算法中的相乘操作可能會超出數(shù)據(jù)范圍，因此可以將相乘操作轉(zhuǎn)化為龜速乘取模。

原理依然是此公式：(a × b) % m = ((a % m) × (b % m)) % m，其中((a % m) × (b % m))即為龜速乘取模。

算法思路：快速冪 + 龜速乘結(jié)合。

//?快速冪取模防止爆炸?(a^b)?%?p
uLL?powerModBig?(uLL?a,?uLL?b,?uLL?p){
????uLL?r?=?1;
????while?(b?!=?0){
????????if?(b?&?1)??//?(b?%?2?==?1)
????????????r?=?mulMod(a,?b,?p)?%?p;
????????b?=?b?>>?1;?//?(b?=?b?/?2)
????????a?=?mulMod(a,?a,?p)?%?p;
????}
????return?r;
}

6. 矩陣乘

#include?<cstdio>
#include?<iostream>
using?namespace?std;

#define?MAX?100

struct?Martix{
????int?row;????//?行?
????int?col;????//?列?
????int?martix[MAX][MAX];
????Martix?(int?r,?int?c):?row(r),?col(c)?{}?//?構(gòu)造函數(shù)，此時不能使用typedef！?
};

Martix?Multiply?(Martix?x,?Martix?y){
????Martix?z(x.row,?y.col);

????for?(int?i?=?0;?i?<?z.row;?i++){
????????for?(int?j?=?0;?j?<?z.col;?j++){
????????????z.martix[i][j]?=?0;
????????????for?(int?k?=?0;?k?<?x.col;?k++)
????????????????z.martix[i][j]?+=?x.martix[i][k]?*?y.martix[k][j];
????????}
????}

????return?z;
}

int?main(){
????int?r,?c;

????printf("請輸入第一個矩陣的行和列：\n");
????scanf("%d?%d",?&r,?&c);
????Martix?x(r,?c);
????printf("請輸入%d行%d列的矩陣：\n",?r,?c);
????for?(int?i?=?0;?i?<?x.row;?i++)
????????for?(int?j?=?0;?j?<?x.col;?j++)
????????????scanf("%d",?&x.martix[i][j]);

????printf("請輸入第二個矩陣的行和列：\n");
????scanf("%d?%d",?&r,?&c);
????Martix?y(r,?c);
????printf("請輸入%d行%d列的矩陣：\n",?r,?c);
????for?(int?i?=?0;?i?<?y.row;?i++)
????????for?(int?j?=?0;?j?<?y.col;?j++)
????????????scanf("%d",?&y.martix[i][j]);

????Martix?result?=?Multiply(x,?y);

????printf("結(jié)果是：\n");
????for?(int?i?=?0;?i?<?result.row;?i++){
????????for?(int?j?=?0;?j?<?result.col;?j++)
????????????printf("%d?",?result.martix[i][j]);
????????printf("\n");
????}

????return?0;
}

7. 矩陣快速冪

#include?<cstdio>
#include?<iostream>
using?namespace?std;

#define?MAX?100

struct?Martix{
????int?row;????//?行?
????int?col;????//?列?
????int?martix[MAX][MAX];
????Martix?(int?r,?int?c):?row(r),?col(c)?{}?//?構(gòu)造函數(shù)?
};

Martix?Multiply?(Martix?x,?Martix?y){
????Martix?z(x.row,?y.col);

????for?(int?i?=?0;?i?<?z.row;?i++){
????????for?(int?j?=?0;?j?<?z.col;?j++){
????????????z.martix[i][j]?=?0;
????????????for?(int?k?=?0;?k?<?x.col;?k++)
????????????????z.martix[i][j]?+=?x.martix[i][k]?*?y.martix[k][j];
????????}
????}

????return?z;
}

Martix?Power?(Martix?x,?int?k){
????Martix?r(x.row,?x.col);

????//?單位矩陣構(gòu)建?
????for?(int?i?=?0;?i?<?r.row;?i++){
????????for?(int?j?=?0;?j?<?r.col;?j++){
????????????if?(i?==?j)
????????????????r.martix[i][j]?=?1;
????????????else
????????????????r.martix[i][j]?=?0;
????????}
????}

????//?矩陣快速冪?
????while?(k?!=?0){
????????if?(k?&?1)
????????????r?=?Multiply(x,?r);
????????k?=?k?>>?1;
????????x?=?Multiply(x,?x);
????}

????return?r;
}

int?main(){
????int?r,?k;

????printf("請輸入行（列）：\n");
????scanf("%d",?&r);
????Martix?x(r,?r);
????printf("請輸入%d行%d列的矩陣：\n",?r,?r);
????for?(int?i?=?0;?i?<?x.row;?i++)
????????for?(int?j?=?0;?j?<?x.col;?j++)
????????????scanf("%d",?&x.martix[i][j]);

????printf("請輸入指數(shù)k：\n");
????scanf("%d",?&k);

????Martix?result?=?Power(x,?k);

????printf("結(jié)果是：\n");
????for?(int?i?=?0;?i?<?result.row;?i++){
????????for?(int?j?=?0;?j?<?result.col;?j++)
????????????printf("%d?",?result.martix[i][j]);
????????printf("\n");
????}

????return?0;
}

8. 矩陣快速冪用于遞推式

斐波那契數(shù)列

數(shù)列遞推式：

矩陣遞推式：

矩陣公式：

#include?<cstdio>
#include?<iostream>
using?namespace?std;

#define?MAX?100

struct?Martix{
????int?row;????//?行?
????int?col;????//?列?
????int?martix[MAX][MAX];
????Martix?(int?r,?int?c):?row(r),?col(c)?{}?//?構(gòu)造函數(shù)?
};

Martix?Multiply?(Martix?x,?Martix?y){
????Martix?z(x.row,?y.col);

????for?(int?i?=?0;?i?<?z.row;?i++){
????????for?(int?j?=?0;?j?<?z.col;?j++){
????????????z.martix[i][j]?=?0;
????????????for?(int?k?=?0;?k?<?x.col;?k++)
????????????????z.martix[i][j]?+=?x.martix[i][k]?*?y.martix[k][j];
????????}
????}

????return?z;
}

Martix?Power?(Martix?x,?int?k){
????Martix?r(x.row,?x.col);

????//?單位矩陣構(gòu)建?
????for?(int?i?=?0;?i?<?r.row;?i++){
????????for?(int?j?=?0;?j?<?r.col;?j++){
????????????if?(i?==?j)
????????????????r.martix[i][j]?=?1;
????????????else
????????????????r.martix[i][j]?=?0;
????????}
????}

????//?矩陣快速冪?
????while?(k?!=?0){
????????if?(k?&?1)
????????????r?=?Multiply(x,?r);
????????k?=?k?>>?1;
????????x?=?Multiply(x,?x);
????}

????return?r;
}

int?main(){
????int?k;

????while?(scanf("%d",?&k)?!=?EOF){?
????????//?斐波那契數(shù)列的遞推矩陣構(gòu)建?
????????//?[1,?1]
????????//?[1,?0]
????????Martix?e(2,?2);
????????e.martix[0][0]?=?1;?e.martix[0][1]?=?1;
????????e.martix[1][0]?=?1;?e.martix[1][1]?=?0;

????????Martix?result?=?Power(e,?k);

????????for?(int?i?=?0;?i?<?result.row;?i++){
????????????for?(int?j?=?0;?j?<?result.col;?j++)
????????????????printf("%d?",?result.martix[i][j]);
????????????printf("\n");
????????}
????}

????return?0;
}

輸入和輸出：

1
1?1
1?0
2
2?1
1?1
3
3?2
2?1
4
5?3
3?2
5
8?5
5?3
6
13?8
8?5
7
21?13
13?8
8
34?21
21?13
9
55?34
34?21
10
89?55
55?34

相關(guān)題目：（POJ3070）斐波那契數(shù)列f(n)，輸入n，求f(n) % 10000，n <= 1e9。

解題思路：僅需在快速冪函數(shù)中添加% 10000即可。

遞推式的一些套路

（1）數(shù)列遞推式：

矩陣遞推式：

（2）數(shù)列遞推式：

矩陣遞推式：

（3）數(shù)列遞推式：

矩陣遞推式：

參考資料

基礎(chǔ)算法—快速冪詳解

矩陣快速冪（原理+模板）

KY21 遞推數(shù)列

標(biāo)簽：

【僅供測試】快速冪與龜速乘的評論 (共 條)

分享到微博請遵守國家法律
邯郸市| 泰和县| 荔波县| 三门县| 纳雍县| 浦城县| 遵义县| 常德市| 丹东市| 即墨市| 布拖县| 庆云县| 道真| 武强县| 新竹县| 林芝县| 绥宁县| 岱山县| 石阡县| 永清县| 尼玛县| 舒城县| 淳安县| 兰溪市| 讷河市| 化德县| 东乡族自治县| 监利县| 海南省| 泉州市| 广元市| 西乌珠穆沁旗| 新余市| 台江县| 祁阳县| 太原市| 红桥区| 普兰店市| 德化县| 东阳市| 墨竹工卡县|