您好我正在写一个code来计算的是P ^ Q其中
Hi I am writing a code to calculate P^Q where
P, Q are positive integers which can have number of digits upto 100000
我要的结果为
I want the result as
result = (P^Q)modulo(10^9+7)
例如:
P = 34534985349875439875439875349875
Q = 93475349759384754395743975349573495
Answer = 735851262
我尝试使用的伎俩:
I tried using the trick:
(P^Q)modulo(10^9+7) = (P*P*...(Q times))modulo(10^9+7)
(P*P*...(Q times))modulo(10^9+7) = ((Pmodulo(10^9+7))*(Pmodulo(10^9+7))...(Q times))modulo(10^9+7)
由于两个P和Q是非常大的,我应该把它们存储在一个数组,并通过数字做模数字。
Since both P and Q are very large, I should store them in an array and do modulo digit by digit.
是否有这样做的任何有效的方式还是有些数论算法,我很想念?
Is there any efficient way of doing this or some number theory algorithm which I am missing?
在此先感谢
下面是一个比较有效的方法:
Here is a rather efficient way:
1)计算P1 = P模10 ^ 9 + 7
1)Compute p1 = P modulo 10^9 + 7
2)计算Q1 = Q模10 ^ 9 + 6
2)Compute q1 = Q modulo 10^9 + 6
3)则P ^ Q模10 ^ 9 + 7等于P1 ^ Q1模10 ^ 9 + 7。这种平等是因为费马小定理如此。需要注意的是P1和Q1足够小,适合在32位整数,这样你就可以实现二进制exponention与标准的整数类型(intermidiate计算,64位整数类型就足够了,因为初始值适合在32位)。
3)Then P^Q modulo 10^9 + 7 is equal to p1^q1 modulo 10^9 + 7. This equality is true because of Fermat's little theorem. Note that p1 and q1 are small enough to fit in 32-bit integer, so you can implement binary exponention with standard integer type(for intermidiate computations, 64-bit integer type is sufficient because initial values fit in 32-bits).