题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3501

题目大意:给定一个n,求出1到n之间与n不互质的数之和。

题解:

首先利用欧拉函数euler(n)求出n的素因子个数;

又有定理gcd(i, n) = 1 -> gcd(n - i, n) = 1,得出eular(n)*n/2是n所有素因子和;

再用1到n-1的和(n-1)*n/2减去n所有素因子和就是答案了。

#include <cstdio>

const long long MOD = 1000000007;

long long euler(long long n) {
	long long res = 1;
	for (long long i = 2; i*i <= n; ++i)
		if (n % i == 0) {
			res *= i - 1, n /= i;
			while (n % i == 0) res *= i, n /= i;
		}
	if (n > 1) res *= n - 1;
	return res;
}

int main() {
	long long n;
	while (scanf("%I64d", &n), n)
		printf("%I64d\n", ((n - 1)*n/2 - euler(n)*n/2 + MOD) % MOD);
	return 0;
}
转载保留版权:http://haipz.com/blog/i/5859 - 海胖博客