整数快速乘法/快速幂+矩阵快速幂+Strassen算法

一时失言乱红尘 2024-02-17 19:21 190阅读 0赞

快速幂算法可以说是ACM一类竞赛中必不可少，并且也是非常基础的一类算法，鉴于我一直学的比较零散，所以今天用这个帖子总结一下

快速乘法通常有两类应用：一、整数的运算，计算(a*b) mod c 二、矩阵快速乘法

一、整数运算：（快速乘法、快速幂）

先说明一下基本的数学常识：

(a*b) mod c == ( (a mod c) * (b mod c) ) mod c //这最后一个mod c 是为了保证结果不超过c

对于2进制，2n可用1后接n个0来表示、对于8进制，可用公式 i+3*j == n （其中 0<= i <=2 ），对于16进制，可用 i+4*j==n（0 <= i <=3）来推算，表达形式为2i 后接 j 个0。

接下来让我们尽可能简单的描述快速乘法的思想：

发表评论取消回复

表情：

评论列表（有 0 条评论，190人围观）

还没有评论，来说两句吧...

相关阅读

相关整数快速乘法/快速幂+矩阵快速幂+Strassen算法

快速幂[算法][Link 1]可以说是ACM一类竞赛中必不可少，并且也是非常基础的一类算法，鉴于我一直学的比较零散，所以今天用这个帖子总结一下快速乘法通常有两类应用：一、整

一时失言乱红尘/ 2024年02月17日 19:21/ 0 赞/ 191 阅读

相关矩阵快速幂

昨天晚上矩阵小王子给我们讲了一下矩阵快速幂，学习了一下，写了一个模板。 1：思想矩阵快速幂的思想就是跟数的快速幂一样，假如我们要求2^11，次方，我们可以把 11 写成

Love The Way You Lie/ 2022年08月12日 18:30/ 0 赞/ 347 阅读

相关矩阵快速幂

include<cstdio> include<iostream> include<cmath> include<vector> inc

朴灿烈づ我的快乐病毒、/ 2022年06月18日 12:29/ 0 赞/ 385 阅读

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

1，整数快速幂： C++ Code <table style="width:100%;font-family:Consolas, 'Courier New';font-

左手的ㄟ右手/ 2022年06月11日 03:57/ 0 赞/ 449 阅读

相关矩阵快速幂

A为一个方阵，则Tr A表示A的迹（就是主对角线上各项的和），现要求Tr(A^k)%9973。 Input 数据的第一行是一个T，表示有T组数据。每组数据的

谁践踏了优雅/ 2022年06月09日 02:09/ 0 赞/ 354 阅读

相关快速幂和矩阵快速幂

前言新年第一篇技术类的文章，应该算是算法方面的文章的。看标题：快速幂和矩阵快速幂，好像挺高大上。其实并不是很难，快速幂就是快速求一个数的幂（一个数的 n 次方）。

╰+攻爆jí腚メ/ 2022年06月01日 08:10/ 0 赞/ 422 阅读

相关矩阵快速幂+整数快速幂

嗯~ 今天总结一下快速幂的知识点 1.首先讲一下矩阵相乘矩阵A与矩阵B相乘的前提条件：A矩阵的列必须和矩阵B的行相等。若A矩阵是m\p的矩阵，那么B矩阵必定是p\n的

缺乏、安全感/ 2022年05月11日 13:22/ 0 赞/ 475 阅读

相关矩阵/整数快速幂/乘

参考来源： [整数快速乘法，整数快速幂，矩阵快速幂【参考博客】][Link 1] [参考题目 poj 3070][poj 3070] 先说明一下基本的数学常识： >

朱雀/ 2022年03月10日 03:44/ 0 赞/ 387 阅读

相关矩阵快速幂

矩阵快速幂源代码参考博客源代码 include <bits/stdc++.h> using namespace std;

港控/mmm°/ 2021年11月13日 21:18/ 0 赞/ 549 阅读

相关矩阵快速幂

通常我们使用的快速幂是以二为底的，这次就遇到了一道以10为底的快速幂题目；先说下快速幂 long long power(long long a,long long

桃扇骨/ 2021年11月10日 14:31/ 0 赞/ 479 阅读