欧拉定理(称费马-欧拉定理或欧拉 函数定理)
欧拉定理表明,若n,a为正整数,且n,a互素(即gcd(a,n)=1),则
这个定理可以用来简化幂的模运算。比如计算7222的个位数,实际是求7222被10除的余数。7和10互素,且fai(10)=4。由欧拉定理知
所以
则对于(ab^c)%1000000007
已知fai(m)是同1到与m互质的数的个数,故应为100000006。
欧拉定理(称费马-欧拉定理或欧拉 函数定理)
欧拉定理表明,若n,a为正整数,且n,a互素(即gcd(a,n)=1),则
这个定理可以用来简化幂的模运算。比如计算7222的个位数,实际是求7222被10除的余数。7和10互素,且fai(10)=4。由欧拉定理知
所以