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.

 

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.

 

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

 

3

4

0 

 

0

2 

 介绍欧拉函数：（公式推导。能够看相关的资料。此处不提及）

首先我们必需要知道欧拉函数是干什么的

欧拉函数的目的是通过某个特定的规律求出n之前与它互质的数的个数

设φ函数为欧拉函数,那么φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),当中p1, p2……pn为x的

全部质因数(这里说的质因子是种类,不是个数)(比方说12=2*2*3，它的因子都是质数)。x是不为0的整数

那么这道题目就好办了化简上述公式：假设p1....pn是x的质因数

φ(x)=x*((p1-1)/p1)((p2-1)/p2)((p3-1)/p3)((p4-1)/p4)…..((pn-1)/pn)(不用忽略前面另一个x要乘上)

如此以下的代码就是欧拉函数了接下来要说的是，假设我们知道了n之前与它互质的数的和

,那么不互质怎么求。非常easy,前n项和sum(n)=(n+1)*n/2高中的知识点;

接着(不互质的数的和)=sum(n)-(n之前与它互质的数的和)。

那怎样求n之前与它互质的数的和,首先我们应该知道一个定理就是

假设gcd(n,i)=1,那么gcd(n,n-i)=1,如此前n个数中假设i与n互质那么n-i与n也是互质的

如此来，n之前与它互质的数的和=(a1+n-a1)+(a2+n-a2)+(a3+n-a3)+(a4+n-a4)+......(an+n-an)

这不正是(有多少对i与n-i乘以n)就是结果了。而互质的个数我们

又知道了,那么有多少对就是φ(x)/2了,互质的数的和=φ(x)/2*n.

接下来(不互质的数的和)=sum(n)-(n之前与它互质的数的和)就能够求出结果

/*

Author: 2486

Memory: 1408 KB		Time: 15 MS

Language: G++		Result: Accepted

VJ RunId: 4178187		Real RunId: 14209894

*/

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long LL;

const LL mod=1000000007;

LL n;

LL getOL(LL x) {

    LL res=x;

    for(int i=2; i<=sqrt(x); i++) {

        if(x%i==0) {

            res=res/i*(i-1);

            while(x%i==0) {

                x/=i;

            }

        }

    }

    if(x>=2) {

        res=res/x*(x-1);

    }

    return res;

}

int main() {

    while(~scanf("%I64d",&n),n) {

        LL ans1=n*(n+1)/2-n;//n前,所以n不包含在求和内

        LL ans2=getOL(n)*n/2;

        printf("%I64d\n",(ans1-ans2)%mod);

    }

    return 0;

}