2021-09-26
2021/9/28 6:14:10
本文主要是介绍2021-09-26,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
数论
对于像Java也不能处理的大数,存在的问题:一数字大,二计算时间长
对于幂数来说,很容易想到快速幂的办法来解决:
int f(int a,int n) { if(n==1) return 0; int t=f(a,n/2); //分治 if(n%2==1) //奇数情况 return t*t*a; else return t*t;//偶数情况 }
更好的一种位运算做快速幂,时间复杂度也是O(log2 n)
a11= a8+ a2+ a1
11: 1011 (二进制)
11= 8+0+2+1
这个判断利用二进制的位运算很容易判断:
1)n&1,取最后一位,并判断是否是0
2)n>>1,把n右移一位,去掉n的最右面的一位
int f(int a,int n) { int t=a;//不定义也可以 int r=1;//返回结果 while(n) { if(n&1) r*=t;//如果n的这个地方是1,就需要乘以 t*=t;//2,4,8,,, n>>1;//去掉刚刚处理过的一位 } return r; }
快速幂常常涉及到大数,这样的题目通常还会使用取模操作
这里,anmod m=(a mod m)n mod m
if(n&1) r = (t*r) % mod ; t = (t*t) % mod;
矩阵快速幂:
运用了线性代数的知识矩阵乘法.
这篇关于2021-09-26的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南
- 2024-09-26Springboot微服务资料入门教程