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

HDU 3501 Calculation 2：http://acm.hdu.edu.cn/showproblem.php?pid=3501

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

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

更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

#include <stdio.h>
#define LL __int64

int 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\n", sum);
    }

    return 0;
}

///HDU 3501

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索int
， 函数
， hdu1716 排序 oj
， int64_t
， sum
， hdu vector
， 求总和
总和
hdu 3501、calculation、miscalculation、power calculation、fare calculation，以便于您获取更多的相关知识。