hdu Calculation 2(初渉欧拉関数)

http://acm.hdu.edu.cn/showproblem.php?pid=3501
n以下であり、nとは互質でない正の整数の和を求める.
オラ関数は、1〜n−1内のnとの間の相互作用の数の数を解くために使用されます.
拡張子: 1~n-1内とn間の相互質の数の和はeular(n)*n/2である.

#include <stdio.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#define LL long long
#define _LL __int64
using namespace std;

const int mod = 1000000007;

int eular(_LL n)
{
	int ret = n;

	for(int i = 2; i*i <= n; i++)
	{
		if(n%i == 0)
		{
			ret -= ret/i;
			while(n%i == 0)
				n /= i;
		}
	}

	if(n > 1)
		ret -= ret/n;
	return ret;
}

int main()
{
	_LL n;
	while(~scanf("%I64d",&n) && n)
	{
		LL ans = n*(n+1)/2-n;
		ans -= eular(n)*n/2;
		ans %= mod;
		printf("%I64d
",ans);

	}
	return 0;
}