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
Sample Output
题目大意:给你一个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;
}
分享到:
相关推荐
hdu 1695 GCD(欧拉函数+容斥原理).docx
(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数
2-sat---hdu3062,代码详尽,清晰,格式规范,亲测无误。
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
教程来自HDU 的ACM教案,非常好的一个资料
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
算法-欧拉回路(HDU-1878)(包含源程序).rar
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
HDU最全ac代码
hdu 1166线段树代码