杭电3501 http://acm.hdu.edu.cn/showproblem.php?pid=3501
题目大意：求1～N中与N互质的数之和与1～N之和的差值。
欧拉公式拓展：
欧拉公式：
（性质4）
AC代码：
#include <iostream>
#include <cstring>
#include <algorithm>
#include <stdlib.h>
//#define DEBUG
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
ll euler(ll n) { //欧拉公式ll ans=n;for(int i=2;i*i<=n;i++) {if(n%i==0) {ans=ans/i*(i-1);while(n%i==0)n/=i;}}if(n>1) ans=ans/n*(n-1);return ans;}
int main() {ll n=0;while(cin>>n) {if(n==0) return 0;cout<<((n*(n-1)/2) - n*euler(n)/2)%MOD<<endl; //该题可以不分步取模}return 0;
}