同余问题

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

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