题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3501
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description

Given a positive integer N, your task is to calculate the sum of the positive integers less than N which are not coprime to N. A is said to be coprime to B if A, B share no common positive divisors except 1.

Input

For each test case, there is a line containing a positive integer N(1 ≤ N ≤ 1000000000). A line containing a single 0 follows the last test case.

Output

For each test case, you should print the sum module 1000000007 in a line.

Sample Input

3
4
0

Sample Output

0
2

Problem solving report:

Description: 计算比n小的数中，和n不互质的数的和%1000000007。
Problem solving: 如果gcd(n,i)==1，那么gcd(n,n-i)==1
所以，对于n有phi(n)(欧拉函数)个小于n的数与n互质，由上面的公式可以知道，其中一个若为i则存在一个为n-i
那么2者之和为n，这样的一共有phi(n)/2对，故与n互质的所有数的和为n*phi(n)/2
故，与n不互质的数就是(1+n-1)*(n-1)/2-n*phi(n)/2

Accepted Code:

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
long long Euler(long long n) {
    long long ans = n;
    for (int i = 2; i <= n / i; i++) {
        if (!(n % i)) {
            ans = ans / i * (i - 1);
            while (!(n % i))
                n /= i;
        }
    }
    if (n > 1)
        ans = ans / n * (n - 1);
    return ans;
}
int main() {
    long long n;
    while (scanf("%lld", &n), n) {
        long long ans = n * (n - 1) >> 1;
        printf("%lld\n", (ans - (Euler(n) * n >> 1)) % MOD);
    }
    return 0;
}