此题是学习欧拉函数必做的模板题。 介绍一下欧拉函数： 设n为正整数，欧拉函数φ(n)定义为不超过n且与n互质的正整数的个数。 三个引理： 1、对于某一素数p，则φ(p)=p-1 2、对于某一素数p的幂次p^a,φ(p^a)=(p-1)*p^(a-1) 3、对于某一合数n可分解为两个素数之积a*b，则φ(n)=φ(a)*φ(b) 证明： 1、显然 2、... [阅读全文]