; 输入一个正整数N(1 ≤ N ≤ 1000000000)，求1~N-1中所有与N不互质的数的和。两个正整数a和b，如果a和b的最大公约数gcd(a,b)>1，则a与b不互质。由于所求和值较大，输出其模1000000007的结果。
（1）编程思路。
先需明白一个简单的定理：若 gcd(n,i)=1，则 gcd(n,n-i)=1。 即如果n与i互质，则n与n-i一定互质。
因此，本题我们可以先求所有与n互质的数的和sum。由于与n互质的数两两配对（i与n-i）的和为n。这样，
sum=n* phi(n)/2 。 phi(n)是欧拉函数，其值为1~n中所有与n互质的数的个数。由于题目中N值较大，筛法用数组保存不恰当，因此直接采用例1中得源程序2的思路求欧拉函数的值。
求得sum后，输出的答案应为 [(n-1)*n/2-sum] % 1000000007 。
（2）源程序。
#include <stdio.h>
#define MOD 1000000007
int main()
{
__int64 n,t,sum,ans;
int i;
while (scanf("%I64d", &n) && n!=0)
{
sum = n;
t=n;
for (i=2;i*i<=t;i++)
if (t % i == 0) // 找到一个质因数i
{
sum -= sum/i;
while (t % i == 0) // 将质因数i全去掉
t /= i;
}
if (t!=1) sum -= sum/t;
ans=n*(n-1)/2;
sum=n*sum/2;
ans=(ans-sum)% MOD;
printf("%d\n",ans);
}
return 0;
}
将此源程序提交给 HDU 3501 “Calculation 2”，可以Accepted。