小编Bog*_*lad的帖子

我得到数字3和变量'n',可以高达1 000 000 000(十亿).我必须打印答案3^n modulo 100003.我尝试了以下方法:

1. 我尝试使用该函数std::pow(3,n),但它不适用于大型指数(在此过程中无法应用模数).
2. 我尝试实现我自己的函数,将数字3提高到幂n,这样我就可以在需要时应用模数,但是当测试数量非常大时,这种方法被证明太慢了.

3. 最后,我尝试对数字'n'进行素数分解,然后使用'n'因子(以及它们出现的次数)来构建答案,这似乎是我能提出的最佳方法(如果是正确).问题是我会为已经素数很大的数字做些什么？

   所以这些是我的想法,如果有人认为有更好的方法(或者我的方法之一是最优的),我将不胜感激任何指导.