문제
GCD(n,k)=1
교재 풀이
import java.io.*;
public class P11689_GCDNK1 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long n = Long.parseLong(br.readLine());
long result = n;
for (long p = 2; p <= Math.sqrt(n); p++) { // 제곱근까지만 진행
if (n % p == 0) { // p가 소인수인지 확인
result = result - result / p; // 결과 값 업데이트
while (n % p == 0) { // 해당 소인수를 지워줌 2^7*11이라면 2^7을 없애고 11만 남김
n /= p;
}
}
}
if (n > 1) // 아직 소인수 구성이 남아있는 경우
//(반복문에서 제곱근까지만 탐색했기 때문에 1개의 소인수가 누락되는 케이스)
result = result - result / n;
System.out.println(result);
}
}
내 풀이) 24.6.21에 풀다가 한계 느끼고 미완성
import java.util.*;
import java.io.*;
public class Main
{
public static void main(String[] args) throws IOException{
Scanner sc=new Scanner(System.in);
long n=sc.nextLong();
}
}
자연수 n이 주어짐 => GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수
즉 어떤 수 n과 최대공약수가 1인 자연수 k의 개수를 구해라
즉 n과 서로소인 수가 몇 개인지 찾아라
접근법
오일러 피 함수 구현 문제임은 교재를 통해 알고 있다
에라토스테네스와 비슷하게 진행된다고 설명하는데 유추해보면
일단 서로소 구할 범위만큼 배열을 초기화해주고, 이 때 크기는 n+1 느낌으로
아니지. n이 int 범위 밖일 때 이렇게 하면 안 되지
형변환만으론 안 되니까, sqrt(n)정도로 해주는 게 어때?
근데 그러면 a[n]을 출력해야 하는데 ???
범위 어떻게 하지? 교재 개념에선
10의 12제곱이라 int는 2의 31제곱 약 그런데
10의 3제곱의 3제곱은 대략 10의 9제곱까진 담을 수 있지만
그 이상은 못하니 확실히 int로는 안 됨
배열엔 long형은 안 되는데
인덱스와 값이 같으면(소수일 땐)
그 소수의 배수마다 a[i]=a[i]-a[i]/k를 해준다
이를 어디까지 탐색하지? sqrt? 그러지 뭐
이 짓을 계속 반복하다 끝나면
최종 배열이 곧 오일러 피 함수의 값들이고
그 중 a[n]을 출력해서 정답 출력하면 됨
슈도코드
long으로 n을 받음
서로소 구할 범위만큼 배열 a 초기화: 크기는 n+1
for i=2부터 n까지
배열을 인덱스로 초기화해주고
for i=2; i<=sqrt(n);i++
if(a[i]==i)
for j=i;j<=n;j+=i
a[j]=a[j]-a[j]/k
print(a[n])
- 교재 이론 설명대로 에라토스테네스의 체를 응용해서 풀려고 했으나, 이 문제에선 이렇게 푸는 게 아님을 깨닫고 그만 둠
설명
- 에라토스테네스의 체처럼 배열을 만들고 그 다음 뭘 어떻게 하는 게 아님
- 나중에 다시 풀 때 배열 안 만들어도 풀 수 있음을 상기하고 가기