SGU102 Coprimes（欧拉函数）

102. Coprimes

• time limit per test: 0.25 sec.
• memory limit per test: 4096 KB

For given integer N ($1<=N<=10^{4}$) find amount of positive numbers not greater than N that coprime with N. Let us call two positive integers (say, A and B, for example) coprime if (and only if) their greatest common divisor is 1. (i.e. A and B are coprime iff gcd(A,B) = 1).

Input

Input file contains integer N.

Output

Write answer in output file.

Sample Input

9

Sample Output

6

---

链接

https://cn.vjudge.net/problem/SGU-102

题意

求区间[1, n-1]中与n互质的数的数量。

题解

可以直接求解，当然也可以用欧拉函数来做。

对于正整数N,少于或等于N ([1,N]),且与N互质的正整数(包括1)的个数，记作φ(n)。 φ(x)=x(1-1/p(1))(1-1/p(2))(1-1/p(3))(1-1/p(4))…..(1-1/p(n)) ，其中p(1),p(2)…p(n)为x的所有质因数；x是正整数;；φ(1)=1(唯一和1互质的数，且小于等于1)。注意：每种质因数只有一个。φ(10)=10×(1-1/2)×(1-1/5)=4;

代码

Status	Accepted
Time	15ms
Memory	1848kB
Length	372

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int gcd(int a, int b)
{
    int c;
    while (b != 0)
    {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

int main()
{
    int n, cnt = 1;
    scanf("%d", &n);
    for (int i = 2; i < n; ++i)
        if (gcd(n, i) == 1)
            cnt++;
    printf("%d\n", cnt);
}

Status	Accepted
Memory	1860kB
Length	360

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int main()
{
    int n, ans, p;
    scanf("%d", &n);
    ans = n, p = 2;
    while (n != 1)
    {
        if (n % p == 0)
        {
            ans = (ans / p * (p-1));
            while (n % p == 0)
                n /= p;
        }
        p++;
    }
    printf("%d\n", ans);
}

虽然非常水，但是也算复习了欧拉函数。

---

The end.
2018-06-08 星期五