首页 > 代码库 > hdoj 3501 Calculation 2 【欧拉函数】
hdoj 3501 Calculation 2 【欧拉函数】
Calculation 2
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2306 Accepted Submission(s): 976
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
数论什么的最不懂了
代码：
#include <stdio.h>
#include <string.h>
#define LL __int64
#define INF 1000000007
LL oular(LL n){
LL i, ans = n;
for(i = 2; i*i <= n; i++){
if(n%i == 0){
n/=i;
ans -= ans/i;
while(n%i == 0){
n/=i;
}
}
}
if(n > 1) ans -= ans/n;
return ans;
}
int main(){
LL n;
while(scanf("%I64d", &n), n){
LL ans = n*(n-1)/2;
printf("%I64d\n", (ans-(n*oular(n)/2))%INF);
}
return 0;
}hdoj 3501 Calculation 2 【欧拉函数】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。