10^9+7 问题

在算法类的问题中，当一个数的值比较大时，很多情况下都会需要把得到的结果除以10^9+7，将余数输出出来。选择10^9+7的原因很简单，因为它是一个质数。
如果这种算法是通过求一个数的幂来实现的，最后可能就会非常耗费时间。比如当幂次高达上万时，先求出结果，再求余数往往是不现实的。因此，针对对于这类求幂的余数的问题，特地写出一种算法，以降低程序运行的时间。
题目：
输入一个数x，以及幂次y，一个质数p，求（x^y mod p), 要求时间复杂度为O（log（y））。
示例：
Input：x=2，y=3，p=5
Output：1 Input: x=5, y=10000, p=1000000007
Output:1
思路：根据 ab mod p=(a mod p)*(b mod p)，将原来的的求幂完之后再进行求余的算法，改进成，每乘两次进行一次求余运算。
代码： def power(x, y, p): res = 1 # Initialize result x = x % p #Update x if it is more than or # equal to p while (y > 0): # If y is odd, multiply x with result if (y & 1): res = (res*x) % p y=y-1 # y must be even now y = y>>1 # y = y/2 x = (x*x) % p return res 运行结果良好。