`

hdu 3501 Calculation 2(欧拉函数的引申)

阅读更多

Calculation 2

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 840    Accepted Submission(s): 371

Problem Description
Given a positive integer N, your task is to calculate the sum of the positive integers less than N which are not coprime to N. A is said to be coprime to B if A, B share no common positive divisors except 1.
Input
For each test case, there is a line containing a positive integer N(1 ≤ N ≤ 1000000000). A line containing a single 0 follows the last test case.
Output
For each test case, you should print the sum module 1000000007 in a line.
Sample Input
3 4 0

 

Sample Output
0 2
 

        题目大意:给你一个N,求小于等于N的不互质的数的总和。

     欧拉公式的引伸小于或等于n的数中,与n互质的数的总和为:φ(x) * x / 2(n>1)

所以:res = n*(n-1)/2-n - phi[x]*x/2。

        主要考对欧拉公式和欧拉定理的推广和理解,不多说,代码。

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

代码:

 

#include <iostream>
#include <stdio.h>
#include <memory.h>
using namespace std;

typedef long long LL;

int eular(LL n)     //欧拉函数
{
    int i, ans = n;
    for(i = 2; i * i <= n; i++)
    {
        if(n%i == 0)
        {
            ans -= ans/i;
            while(n%i == 0)
                n /= i;
        }
    }
    if(n > 1) ans -= ans/n;

    return ans;
}

int main()
{
    LL n, ans;
    while(scanf("%I64d", &n), n)
    {
        ans = n * (n+1) / 2 - n;    //总和
        ans -= eular(n) * n / 2;    //减去互质的总和公式
        ans %= 1000000007;          //再取模
        printf("%I64d\n", ans);
    }

    return 0;
}

 

0
0
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics