数论 欧拉降幂+费马小定理+指数循环节
题目链接：https://ac.nowcoder.com/acm/contest/330/E
题目大意：求2^a%1000000007。
和队友一直怼快速幂。然后T了。后来发现这个余数应该是循环的，我当时认为循环节是1000000007。后来才知道发现是1000000006。
让我们来复习一下费马小定理：
2与1000000007互质。2 ^ 0 = 2 ^ (p-1) 所以循环节为(p-1-0)=1000000006。
2 ^ a%1000000007 = 2 ^ （a%1000000006) %1000000007。
当然还可以用欧拉降幂：
结果不出我所料：1000000007的欧拉函数就是1000000006。
投递美团等公司10个岗位 >