bzoj2705

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

27 8月 2015

2705: [SDOI2012]Longge的问题

Description

Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i, N)(1<=i <=N)。

Input

一个整数，为N。

Output

一个整数，为所求的答案。

Sample Input

Sample Output

HINT

【数据范围】

对于60%的数据，0<N<=2^16。

对于100%的数据，0<N<=2^32。

Source

round1 day1

题目类型：欧拉函数

算法分析：枚举N所有的约数x，则如果知道gcd(i, N) = x(1 <= i <= N)的个数，直接将其乘以x累加起来就是答案。而gcd (i, N) = x可以转换为gcd (i / x, N / x) = 1，而后者的个数可以由欧拉函数求解得到。注意本问题不需要枚举所有的约数，只需要枚举所有小于等于sqrt(N)的约数即可，因为大于sqrt (N)的约数可以由小于sqrt(N)的约数计算得到，这样时间复杂度就是O(sqrt (N))的

#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 = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 100 + 666;

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");

    int n;
    while (cin >> n)
    {
        long long tot = 0;
        for (int i = 1; i * i <= n; i++)
        {
            if (n % i == 0)
            {
                tot += i * GetEuler (n / i);
                if (i * i < n)
                    tot += (n / i) * GetEuler (i);
            }
        }

        cout << tot << endl;
    }

return 0;
}

#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 = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 100 + 666;

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");

int n;

while (cin >> n)

{

long long tot = 0;

for (int i = 1; i * i <= n; i++)

{

if (n % i == 0)

{

tot += i * GetEuler (n / i);

if (i * i < n)

tot += (n / i) * GetEuler (i);

}

cout << tot << endl;

}

return 0;

}

bzoj2190

bzoj2818

一	二	三	四	五	六	日
« 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

超客的水墨烟雨