explanation
(a+b) % p = (a%p + b%p) % p
(a-b) % p = (a%p - b%p) % p
(ab) % p = (a%p b%p) % p
(a^b) %p = ((a%p) ^ b) %p
if n is even,
a^n % b = (a^n/2 a^n/2) % b = ((a^n/2 % b) (a^n/2 % b)) % b
if n is odd,
a^n % b = (a^n/2 a^n/2 a) % b = ((a^n/2 % b) (a^n/2 % b) (a % b)) % b
注意Integer overflow的问题
code
1 |
public class { |
近期评论