首先看一个简单的东西。
若gcd(i,n)=1，则有gcd(n-i,n)=1。
于是在小于N且与N互质的数中，i与n-i总是成对存在，且相加等于n。
考虑i=n-i的特殊情况，此时n=2*i，由gcd(i,n)=1，得n=2。此时手动计算ans=1。
因为小于N且与N互质的数的个数为φ(n)，于是我们可以得出公式ans=n*φ(n)/2。
一个简单的公式——求小于N且与N互质的数的和
原文：http://www.cnblogs.com/halfrot/p/7413181.html
