动力模组高尔夫。

Question

编写一个函数f(a，b，c)，在10秒钟内计算a^b (mod c)。

• a，b< 10^100
• C< 10000。

例子：

f(10^50, 10^50, 54123) = 46555
f(5^99, 10^99, 777) = 1

Answer 1

dc 1或5 chars

在GNU中，有一个操作符|，它就是这样做的。引用自手册：

|弹出三个值并计算一个模幂。弹出的第一个值用作缩减模数；这个值必须是一个非零数，并且应该是一个整数。第二个弹出式作为指数；这个值必须是一个非负数，并且这个指数的任何分数部分都将被忽略。弹出的第三个值是得到指数的基，它应该是一个整数。对于小整数，这类似于序列Sm ^ Lm%，但与^不同，此命令将适用于任意大的指数。

您可以将它指定为“函数”如下：

[|]sf

(也有5个字符.)这将|分配给f。你可以把它叫做lfx。

Answer 2

Python-5 chars

f=pow

测试

>>> f(10**50, 10**50, 54123)
46555L
>>> f(5**99, 10**99, 777)
1L

Answer 3

Haskell，65岁，

冒昧地只在二进制b的设置位上取模数，但给定范围限制，这不是问题。

f a b c|b==0=1|odd b=mod(a*f a(b-1)c)c|0<1=f(mod(a^2)c)(div b 2)c