[C++] 11689번 GCD(n, k) = 1 - 수학, 정수론, 오일러 피 함수

1. 문제를 읽고 이해한다.

자연수 n \(1\leq n\leq 10^{12}\)

GCD(n, k) = 1을 만족하는 자연수 $$ 1 \leq  k  \leq n $$ 의 개수 출력

2. 문제를 익숙한 용어로 재정의한다.

n과 서로소인 수의 개수 출력(1도 포함)

3. 어떻게 해결할지 계획을 세운다.

1. 에라토스테네스의 체로 소수를 구하기( $$ \sqrt{n} $$ 가지) O( $$ \sqrt{n} $$ )
2. 오일러 피 하수(Euler phi function)을 사용하기

4. 계획을 검증한다.

O( $$ \sqrt{n} $$ ) = $$ \10^{6} $$ = 1, 000, 000

5. 프로그램으로 구현한다.

6. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다.

• n과 서로소가 아니라 n의 소인수를 구해야 한다.
• $$ \sqrt{n} $$개의 배열이 아닌 +1개의 배열이 필요하다.
• ll(long long)의 범위를 넘어간다.
• 2씩 +해서 탐색하면 짝수를 모두 제거해서 소요 시간을 획기적으로 줄일 수 있다.

 

 

결국 여차 저차 해서 완성된 코드

#include <iostream>
#include <math.h>

using namespace std;
typedef long long ll;

ll N;

ll pi()
{
    //sqrt(N)까지만 소수를 확인해주면 나머지 소수도 확인할 수 있다.
    ll ans = N;
    int sqrtn = int(sqrt(N));
    for(int i=2; i<=sqrtn; ++i) {
        //N이 i로 처음으로 나눠질 경우 i는 소수이다.
        if(!(N%i)) {
            //i를 소인수로 더 이상 가지지 않을 때까지 N을 나눠준다.
            while(!(N%i)) N/=i;
            ans = ans - ans/i;
        }
    }
    //sqrt(N)보다 큰 소수가 있을 수 있으므로 한 번더 나눠준다.
    if(N>1)
        ans = ans - ans/N;
    return ans;
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    
    cin >> N;
    cout << pi();
    
    return 0;
}

 

 

 

 

 

<오일러 피 함수 1>

https://m.blog.naver.com/hongjg3229/221795417061

오일러 파이 함수와 오일러 정리

 

<에라토스테네스의 체>

https://velog.io/@max9106/Algorithm-%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B2%B4

[Algorithm] 에라토스테네스의 체

 

<짝수를 제거한 코드(풀어야 볼 수 있습니다.)

https://www.acmicpc.net/source/15488257

로그인

 

 

 

 

 

 

 

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.