杭电上有一道十分让初学者十分蛋疼的题 a^b%m,看似很简单,但题目要求b的范围是(0,1000000000],a是32位整数范围,m是小于40000的整数。咋一看这题,貌似要用高精度。但是赤裸裸的用高精度的话,在空间复杂度以及时间复杂度上都是伤不起的!!
让我们来换个思路,有一定数学基础的人都知道,(a*b)%m 是等价于 a%m * b%m的,这样好了,可以不用高精度了,但是完全模拟的话,在规定时间内是不可能出解的。
我们再想想,是否可以减小计算量呢?有了!我们可以将 a^b 分解成为 t1*a^1+t2*a^2+t3*a^3+.....(ti=0 或者 1),我们预处理下,算出a^2i,然后将b变为二进制,乘以相应的项,我们就得到了最后的结果。运算次数大大减少了,这样是可以在规定时间内出解的。
如果我们觉得上面的方法太麻烦的话,下面的递归代码就十分简单了。
#include<iostream>
using namespace std;
int run(int a,int b,int m){
int t;
if (b==1) return a%m;
if (b&1){
t=run(a,b/2,m);
return ((t*t%m)*a)%m;
}else{
t=run(a,b/2,m);
return (t*t)%m;
}
}
int main(){
int a,b,m;
cin >> a >> b >> m ;
cout << run(a,b,m);
system("pause");
return 0;
}
这其实是利用了一个分治的思想,要想求a^b1,先求出a^b2(其中b2=b1/2),而要求a^b2,又得求出a^b3(其中b3=b2/2)..........直到bi =1。整个问题的时间复杂度就变得非常低了。最多几十次基本操作就能得到结果(有木有感觉很神奇)。其实我们还可以将这个算法求斐波拉契数列的第10000000项对m取余,这样用到矩阵的乘法,下面给出具体的矩阵推导以及代码。
#include<iostream>
using namespace std;
class Matrix{
public:
int width,height;
Matrix(){
}
Matrix(int hei,int wid){
width = wid; height = hei;
v = new int*[height];
for (int i=0;i<height;i++)
v[i] = new int[width];
}
void set(int hei,int wei){
v = new int*[height];
for (int i=0;i<height;i++)
v[i] = new int[width];
}
int** v;
friend Matrix operator*(Matrix a,Matrix b){
Matrix res(a.height,a.width);
//确保数据正确
//if (a.width!=b.height) retutn res;
for (int i=0;i<a.height;i++){
for (int j=0;j<a.width;j++){
int ans = 0;
for (int k=0;k<a.width;k++){
ans += a.v[i][k]*b.v[k][j];
}
res.v[i][j] = ans;
}
}
return res;
};
friend Matrix operator%(Matrix a,int m){
Matrix ans(a.height,a.width);
for (int i=0;i<a.height;i++)
for (int j=0;j<a.width;j++)
ans.v[i][j] = a.v[i][j] % m;
return ans;
}
};
Matrix a(2,2);
Matrix run(int b,int m){
Matrix t;
if (b==1) return a%m
;
if (b&1){
t=run(b/2,m)%m;
return ((t*t)*a)%m;
}else{
t=run(b/2,m)%m;
return (t*t)%m;
}
}
int main(){
int n,m;
while(1){
cin >> n >> m;
a.v[0][0] = 0; a.v[0][1] = 1; a.v[1][0] = 1; a.v[1][1] = 1;
Matrix ans;
ans = run(n,m);
for (int i=0;i<ans.height;i++){
for (int j=0;j<ans.width;j++)
cout << ans.v[i][j] << " ";
cout << endl;
}
}
system("pause");
return 0;
}
分治就是分而治之的缩写,分治的思想并不局限于这道题,它能极大的提高算法的效率。所以掌握它是十分必要的。
- 大小: 68.4 KB
分享到:
相关推荐
五大常用算法-动态规划,分治,递归,贪心,回溯
2021-算法设计与分析-02-递归与分治-2.pdf
OTSU算法也称最大类间差法,有时也称之为大津算法,被认为是图像分割中阈值选取的最佳算法,计算简单,不受图像亮度和对比度的影响,因此在数字图像处理上得到了广泛的应用。它是按图像的灰度特性,将图像分成背景和...
算法分析与设计 课程中分治策略的典型例子,采用MFC文档编程可视化实现算法; 能够手动进行对棋盘的颜色填充,并能显示棋盘中的填充数值。 由于这是课程作业,时间紧而赶制的,封装性可能比较差。 我用的版本是C++...
分治算法是计算科学的一个经典算法,主要也是用了递归
学 习a c m 分 治算法 的入门 教程简单易学acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法vacm分治算法acm...
算法-分治- 二分法(包含源程序).rar
算法-分治- 莫队算法- 普通莫队(包含源程序).rar
数据结构与算法-五大常用算法总结(分治法,回溯法,分治限界法,贪心算法,动态规划法),算法数据结构 五大常用算法
模拟退火算法-python实现 模拟退火算法-python实现 模拟退火算法-python实现 模拟退火算法-python实现 模拟退火算法-python实现 模拟退火算法-python实现 模拟退火算法-python实现 模拟退火算法-python实现 模拟退火...
算法实验代码和报告(时间复杂度、0-1背包问题、分治与贪心、蛮力法)。
算法-分治- 莫队算法- 带修莫队(包含源程序).rar
收敛熟度快,求解效果好。%-------nCity:城市数量...%-------generation:算法终止条件一,迭代代数; %-------nR:算法终止条件二,最短路径值连续nR代不变; %-------R:最短路径; %-------Rlength:最短路径长度。
%-------nCity:城市数量; %-------xyCity:城市二维坐标; %-------dCity:城市间距离矩阵; %-------nPopulation:种群个体数量; %-------Population:种群,nPopulation*nCity矩阵,每行由{1,2,...,nCity}某一...
基于用户的协同过滤推荐算法--开题报告.pdf基于用户的协同过滤推荐算法--开题报告.pdf基于用户的协同过滤推荐算法--开题报告.pdf基于用户的协同过滤推荐算法--开题报告.pdf基于用户的协同过滤推荐算法--开题报告.pdf...
%%感知机学习算法---原始形式 %%算法步骤: % 1.选取初值w0,b0.确定学习率(属于(0,1]) % 2.在训练集中选取数据(xi,yi) % 3.如果yi(w*xi+b),更新w,b % w=w+学习率*yi*xi % b=b+学习率*yi % 4.转至(2),直到...
用粒子群算法计算最短路径,一般用于车辆路径问题%------基本粒子群优化算法(Particle Swarm Optimization)----------- %------名称:基本粒子群优化算法(PSO) %------作用:求解优化问题 %------说明:全局性,...
算法设计策略 - 05-2 分治法.pdf
银行家算法-javascript实现.zip 银行家算法-javascript实现.zip银行家算法-javascript实现.zip银行家算法-javascript实现.zip银行家算法-javascript实现.zip银行家算法-javascript实现.zip银行家算法-javascript实现...
旅行商问题-A算法-java