大佬教程收集整理的这篇文章主要介绍了将数字提高到巨大的指数,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
利用模块化算术的特性
(a × b) modulo M == ((a module M) × (b modulo M)) modulo M
通过使用上述乘法规则
(a^n) modulo M
= (a × a × a × a ... × a) modulo M
= ((a module M) × (a modulo M) × (a modulo M) ... × (a modulo M)) modulo M
通过分治法计算结果。重复关系将是:
f(x, n) = 0 if n == 0
f(x, n) = (f(x, n / 2))^2 if n is even
f(x, n) = (f(x, n / 2))^2 * x if n is odd
这是C ++实现:
int powerUtil(int base, int exp, int mod) {
if(exp == 0) return 1;
int ret = powerUtil(base, exp / 2, mod) % mod;
ret = 1LL * ret * ret % mod;
if(exp & 1) {
ret = 1LL * ret * base % mod;
}
return ret;
}
double power(int base, int exp, int mod) {
if(exp < 0) {
if(base == 0) return DBL_MAX; // undefined
return 1 / (doublE) powerUtil(base, -exp, mod);
}
return powerUtil(base, exp, mod);
}
给我数字3和一个变量’n’,它可以高达1000000000000(十亿)。我必须打印的答案3^n modulo 100003
。我尝试了以下方法:
std::pow(3,n)
,但不适用于大指数(在处理过程中无法应用模数)。因此,这些就是我的想法,如果有人认为有更好的方法(或者我的方法之一是最佳方法),我将不胜感激。
以上是大佬教程为你收集整理的将数字提高到巨大的指数全部内容,希望文章能够帮你解决将数字提高到巨大的指数所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。