ACM 数论
因为博客上写公式不方便，所以选择了纸上写 懒 ！
目录
快速幂
欧几里得算法
快速幂
顾名思义，快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N)， 与朴素的O(N)相比效率有了极大的提高。 —— 《百度百科》
通过将指数转化为二进制的方式，结合位运算加速求幂的过程
思路
代码实现
递归
int quick_pow(int a,int b) { if(b == 0) return 1; int res = quick_pow(a , b / 2); if(b % 2 != 0) { return res * res * a; } return res * res; }
非递归
int quick_pow(int a,int b) { int res = 1; while(b) { if(b & 1)//若此时b的二进制位为1 ，则需要乘以a的（2的i次方） { res = res * a; } a = a * a;//将a的（2的i次方）转化为a的（2的i+1次方） b >>= 1;//将判断过后的b的二进制位右移删去 } return res; }
快速幂取模
有时题目需要对快速幂取模，此时只需要在快速幂的基础上，每次乘法后取一下模即可
int quick_pow(int a,int b,int mod) { int res = 1; while(b) { if(b & 1) { res = res * a % mod; } a = a * a % mod; b >>= 1; } return res; }
欧几里得算法
用于给定整数 a, b 求 a 和 b 的最大公约数，也可用于判断两数是否互质，若两数的 gcd 为 1，则两数互质
证明
代码实现
非递归写法
int gcd(int a, int b){ while(b) { int tmp = a; a = b; b = tmp % b; } return a; }
递归写法
int gcd(int a, int b){ //return b == 0 ? a : gcd(b , a % b);//也可以通过这种写法压行，效果是一样的 if(b == 0) return a; return gcd(b , a % b); }
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
