首页 > 其他 > 详细

hdoj 3501 Calculation 2 【欧拉函数】

时间:2014-11-11 19:13:23      阅读:213      评论:0      收藏:0      [点我收藏+]

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 【欧拉函数】

原文:http://blog.csdn.net/shengweisong/article/details/41014079

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!