bzoj2190

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

27 8月 2015

2190: [SDOI2008]仪仗队

Description

作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。　现在，C君希望你告诉他队伍整齐时能看到的学生人数。

Input

共一个数N。

Output

共一个数，即C君应看到的学生人数。

Sample Input

Sample Output

HINT

【数据规模和约定】　　对于 100% 的数据，1 ≤ N ≤ 40000

Source

数论

题目类型：欧拉函数

算法分析：本题其实要求解的是gcd (i, j) = 1 (1 <= i, j <= N)的个数，可以直接枚举i，然后求解phi (i)的值并累加起来，最后再将结果乘以2加上对角线上的个数1

#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;
        n--;
        for (int i = 1; i <= n; i++)
            tot += GetEuler (i);

        cout << tot * 2 + 1 << 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;

n--;

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

tot += GetEuler (i);

cout << tot * 2 + 1 << endl;

}

return 0;

}

sgu112

bzoj2705

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

超客的水墨烟雨