algorithm - 为什么我们应该在 GP 求和公式中使用模乘逆？

Question

问题： https ://www.codechef.com/ISCC2018/problems/T24 我提到的代码： https ://www.codechef.com/viewsolution/19340066

在这个问题中，我们应该找到几何级数的总和。在cpp中使用几何级数公式的求和时，为什么需要找到K-1的模乘逆？为什么我们不能直接除以K-1？

几何级数：k+(k k)+(k k*k)+.....直到 n 项（其中 k 是某个整数） 公式：（第一项 *（Cd 的 n - 1 次幂））/（Cd -1)。Cd指几何级数的共同差。

标签： algorithm

Answer 1

如果使用高精度整数，除以 K-1 将给出正确答案。

问题是 K 的 N 次方会非常大。K 可以达到 10 亿，N 可以达到 10 亿，因此 K 的 N 次方可以是 90 亿位数字。

但是，只要求以素数为模的结果，因此可以通过以该素数为模进行所有计算来避免高精度整数。