4924번 - 정수론 싫어 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 181 | 77 | 56 | 42.105% |
문제
정수론 중간고사를 마치고 집으로 돌아온 상근이는 패닉에 빠졌다. 유일하게 공부를 하지 않은 것이 오일러 피 함수(Euler's totient function, \(\varphi \))였는데, 그 함수에 관한 문제만 나왔기 때문이다. 상근이는 너무 억울했고, 직접 Totient 함수를 만들기로 했다.
정수론에서 양의 정수의 소인수는 그 정수를 나머지 없이 나눌 수 있는 소수이다. 상근이는 $n \ge 2$에서 함수 $F(n)$을 곱이 $n$이 되는 감소하지 않는 소수의 리스트로 정의했다. 예를 들어, $F(8) = \ll 2,2,2 \gg$, $F(60) = \ll 2,2,3,5 \gg$, $F(71) = \ll 71 \gg$ 이다. $O(n)$은 $F(n)$의 길이이다. 예를 들어, $O(8) = 3$, $O(60) = 4$, $O(71) = 1$ 이 된다. 마지막으로, 양의 정수에 대해서 \(p(n)\)을 다음과 같이 정의했다.
\(p(n) = \begin{cases} 0 & \text{if } n = 1 \\ -1 & \text{if } n \text{ is a prime number} \\ O(n) & \text {otherwise} \end{cases}\)
아래 표에는 \(p(n)\)의 첫 20개 값이 나와있다.
| $n$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | $11$ | $12$ | $13$ | $14$ | $15$ | $16$ | $17$ | $18$ | $19$ | $20$ |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $p(n)$ | $0$ | $-1$ | $-1$ | $2$ | $-1$ | $2$ | $-1$ | $3$ | $2$ | $2$ | $-1$ | $3$ | $-1$ | $2$ | $2$ | $4$ | $-1$ | $3$ | $-1$ | $3$ |
$a \le b$를 만족하는 두 양의 정수 $a$와 $b$에 대해서, 상근이는 자신의 Totient 함수인 \(\varphi(a,b)\)를 다음과 같이 정의했다.
\(\varphi (a,b)= ( \sum _{ k=a }^{ b }{ p(k) } ) - (b-a+1)\)
예를 들어, \(\varphi(1,4) = -4\), \(\varphi(16,16) = 3\), \(\varphi(8,12) = 4\) 이다.
구간 $[L, U]$가 주어졌을 때, 가장 큰 값을 갖는 \(\varphi\)를 찾는 프로그램을 작성하시오.
즉, $L \le U$를 만족하는 두 양의 정수 $L$과 $U$가 주어졌을 때, 가장 큰 \(\varphi(a,b)\) ($L \le a \le b \le U$) 를 찾는 프로그램을 작성하시오. 예를 들어, 구간 $[1,20]$에서 가장 큰 \(\varphi\)는 7이다. (\(\varphi(8,16)\))
입력
입력은 7,000개 이하의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, $L$과 $U$가 주어진다. ($1 \le L \le U < 1,000,000$)
입력의 마지막 줄에는 $-1$이 두 개 주어진다.
출력
각 테스트 케이스마다 주어진 구간 $[L, U]$에서 찾을 수 있는 가장 큰 \(\varphi\) 값을 출력한다.
예제 입력 1
1 5 1 20 10 20 900000 901000 -1 -1
예제 출력 1
1. 1 2. 7 3. 5 4. 2551
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호