同余问题

atttx123

对于(aⁿ)/b mod p 有无快速的得值方法？其中aⁿ可能会很大

mathe

只要p不是很大就很简单. 比如你可以直接试用一下gxqcn的HugeCalc看看,计算效率很高的. 通常使用的算法如下: 比如你要计算$a^100(mod p)$ 那么可以计算 $a_1-=a(mod p)$ $a_2-=a_1^2(mod p)$ $a_4-=a_2^2(mod p)$ $a_8-=a_4^2(mod p)$ $a_16-=a_8^2(mod p)$ $a_32-=a_16^2(mod p)$ $a_64-=a_32^2(mod p)$ 然后由于 $a^100-=a^64*a^32*a^4-=a_64*a_32*a_4(mod p)$ 至于除法直接使用广义辗转相除法计算数论倒数就可以了

atttx123

谢谢，小弟我明白了，谢谢老大