@[迟陌](/user/160870) 同一个子问题反复递归肯定会超时啊
by YC_George @ 2023-11-23 16:33:54
这个复杂度是假的。
$T(n)=2T(\dfrac{n}{2})+O(1)=O(n)$。
真的快速幂应该是 $T(n)=T(\dfrac{n}{2})+O(1)=O(\log n)$。
问题就在于 `f(a, b / 2, k)` 调用了两次，其实一次就行。
by wosile @ 2023-11-23 16:43:53
@[wosile](/user/280243) @[wosile](/user/280243) 谢谢大佬！我知道问题在哪儿了orz
by 迟陌 @ 2023-11-23 20:42:20
@[wosile](/user/280243) 其实里面还有个问题就是如果我拿一个long long 存f（）的话会溢出，好像只有把所有有乘号的地方都%了才能过#7
~~（试了unsigned ll但是还是wa了为什么QAQ）~~
但好在AC了，感谢大佬
by 迟陌 @ 2023-11-23 20:57:46