hdu 3501 Calculation 2(欧拉函数的引申)_C/C++_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > C/C++ > hdu 3501 Calculation 2(欧拉函数的引申)

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

 2011/12/8 8:11:54  gzhu_101majia  http://gzhu-101majia.iteye.com  我要评论(0)
  • 摘要:Calculation2TimeLimit:2000/1000MS(Java/Others)MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):840AcceptedSubmission(s):371ProblemDescriptionGivenapositiveintegerN,yourtaskistocalculatethesumofthepositiveintegerslessthanNwhicharenotcoprimetoN
  • 标签:函数

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;
}

?

上一篇: 安装mysql驱动 下一篇: hdu 2588 GCD
发表评论
用户名: 匿名