首页 > 代码库 > HDU3501 Calculation 2 【欧拉函数】
HDU3501 Calculation 2 【欧拉函数】
Calculation 2
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2279 Accepted Submission(s): 969
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
Author
GTmac
Source
2010 ACM-ICPC Multi-University Training Contest（7）——Host by HIT
欧拉函数用来求[1,x)中跟x互质的数的个数。
#include <stdio.h>
#include <string.h>
#include <math.h>
#define mod 1000000007
typedef __int64 LL;
int Euler(int x) {
int i, res = x;
for(i = 2; i <= (int)sqrt((double)x); ++i) {
if(x % i == 0) {
res = res / i * (i - 1);
while(x % i == 0) x /= i; // 保证i一定是素数
}
}
if(x > 1) res = res / x * (x - 1);
return res;
}
int main() {
int n, i;
LL ans;
while(scanf("%d", &n), n) {
ans = (LL)n * (n - 1) / 2 - (LL)Euler(n) * n / 2;
printf("%d\n", ans % mod);
}
return 0;
}HDU3501 Calculation 2 【欧拉函数】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。