MENU

SGU102 Coprimes(欧拉函数)

2018 年 06 月 08 日 • 阅读: 1096 • 数论阅读设置

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;

代码

StatusAccepted
Time15ms
Memory1848kB
Length372
#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);
}
StatusAccepted
Memory1860kB
Length360
#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 星期五