hdu3501

maksyuki 发表于 oj 分类，标签: 数论-欧拉函数

15 9月 2015

Calculation 2

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

Author

GTmac

Source

2010 ACM-ICPC Multi-University Training Contest（7）——Host by HIT

题目类型：Euler函数

算法分析：首先用一下欧拉函数GetEuler(n)求一下1~n中与n互质的质因子的个数，然后就要用到一个比较常用的定理：如果gcd(n,i)==1,那么就有gcd(n,n-i)==1; 于是题目的要求是小于n并且与n不互质的所有数的和，这里我们可以先求与n互质的所有数的和为sum = n*(Euler(n) / 2) 。最后用所有数的和减去sum即可

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const int MOD = 1000000000 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 366 + 6;

long long GetEuler (long long val)
{
    long long ans = val;
    for (long long i = 2; i * i <= val; i++)
    {
        if (val % i == 0)
        {
            ans -= ans / i;

            while (val % i == 0)
            {
                val /= i;
            }
        }
    }

    if (val > 1)
        ans -= ans / val;

return ans;
}

int main()
{
//    ifstream cin("aaa.txt");

    long long n;
    while (cin >> n)
    {
        if (n == 0)
            break;

        long long tot = (1 + n) * n / 2 - n;
        tot -= n * GetEuler (n) / 2;

        cout << tot %MOD << endl;
    }
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const int MOD = 1000000000 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 366 + 6;

long long GetEuler (long long val)

{

long long ans = val;

for (long long i = 2; i * i <= val; i++)

{

if (val % i == 0)

{

ans -= ans / i;

while (val % i == 0)

{

val /= i;

}

if (val > 1)

ans -= ans / val;

return ans;

}

int main()

{

// ifstream cin("aaa.txt");

long long n;

while (cin >> n)

{

if (n == 0)

break;

long long tot = (1 + n) * n / 2 - n;

tot -= n * GetEuler (n) / 2;

cout << tot %MOD << endl;

}

hdu3292

hdu3549

一	二	三	四	五	六	日
« 6月
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

超客的水墨烟雨

hdu3501

Calculation 2

分类目录

标签云

书签

近期评论