HDU 3501 Calculation 2：欧拉函数的应用

HDU 3501 Calculation 2：欧拉函数的应用2015-02-17HDU 3501 Calculation 2：http://acm.hdu.edu.cn/showproblem.php？pid=3501

大意：求1~n之间与n不互质的数的总和。

思路：欧拉函数的应用；先用欧拉函数求出与n互质的总数m，计算m个数的总和，用n的总和减去m的总和就是想要的结果。

#include <stdio.h>#define LL __int64int eular（int n）{int ret = 1;for（int i = 2; i*i <= n;i++）if（n%i == 0）{n /= i, ret *= i-1;while（n%i == 0）n /= i, ret *= i;}if（n > 1）ret *= n-1;return ret;}LL n, m;int main（）{while（~scanf（"%I64d", &n） && n）{LL sum = n*（n+1）/2-n; ///计算所有数总数LL t = eular（n）*n/2; ///计算互质的数总和sum -= t;sum %= 1000000007;printf（"%I64d
", sum）;}return 0;}///HDU 3501

From：cnblogs GLSilence