当前位置：首页 > news >正文

php网站建设设计制作方案seo课程培训课程

news 2025/7/5 17:52:38

php网站建设设计制作方案,seo课程培训课程,如何做融资网站,app软件制作公司排名一般大家写都是 int ans 1; for (int i 1; i < a; i )ans * x;时间复杂度但是这对于我们还不够，我们要首先我们得知道一个数学知识那么求就有以下递归式 a 能被2整除 a 不能被2整除 (这里a/2是整除) 所以每次都调用不就是么最后补充一个东西…

一般大家写 $x^a$ 都是

int ans = 1;
for (int i = 1; i <= a; i ++)ans *= x;

时间复杂度 $O(n)$

但是这对于我们还不够，我们要 $O(logn)$

首先我们得知道一个数学知识

$x^{a^{b}} = x^{a*b}$

那么求 $x^a$ 就有以下递归式

a 能被2整除 $x^a = x^{(a/2)^{2}} = x^{a/2} * x^{a/2}$

a 不能被2整除 $x^a = x^{(a/2)^{2}} * x = x^{a/2} * x^{a/2} * x$ (这里a/2是整除)

所以每次都调用 $a/2$ 不就是 $O(logn)$ 么

最后补充一个东西

$x^a mod b = (x^{i} mod b * x^{j} mod b) mod b$ (i + j = a)

代码：

#include <iostream>
using namespace std;
typedef long long LL;
LL a, b, m;
//m是取模的数
LL q_pow(LL a, LL b, LL m) {if(b == 0)return 1;LL tmp = q_pow(a, b >> 1, m) % m;return (b & 1 ? a : 1) * tmp % m * tmp % m;
//b & 1 和 b % 2 == 1 是等价的
}
int main() {cin >> a >> b >> m;cout << q_pow(a, b, m);return 0;
}

查看全文

http://www.ritt.cn/news/6898.html