欧拉函数的应用

\(欧拉函数的定义\)
欧拉函数，\(\varphi(n)\)，就是\(1\)~\(n\)中和\(n\)互质的数的个数。
\(欧拉函数的应用1\)
求\(1\)到\(n\)中和\(n\)互质的数的和，就是\(n\varphi(n)/2\)。