数论今日发现，模的问题

2019-04-14 16:27发布

站内文章 / 模拟电子
13077 0 919
过于依赖快速幂，实际上还是有优化的空间的，对于a^n%p(p为素数)的情况。实际上，等于：a^(n%(p-1))%p,因为由p为素数，必然满足费马小定理即： a^(p-1)%p=1,那么把a^n的所有的a^(p-1)剥离出来即：a^(n%(p-1))，用它模p效果还是斐然的，不过当p很大时就未必了。 还有一个更一般的就是欧拉函数，只需满足：a与p互素即可。

热门文章