Common Factors

시간 제한1초메모리 제한1024 MB

요약

2 ≤ k ≤ n인 k 중에서 [1, k]의 정수 가운데 k와 1보다 큰 공약수를 가지는 비율이 가장 큰 k를 찾아 기약분수로 출력한다.

난이도: 보통10점 중 7점
유형: 정수론, 수학
정답자: 아직 제출이 없습니다

문제

Everyone likes to share things in common with other people.

Numbers are the same way! Numbers like it when they have a factor in common.

For example, $4$ and $6$ share a common factor of $2$ , which gives them something to talk about.

For a given integer $n$ , we define a function, $f(n)$ , equal to the number of integers in the range [ $1$ , $n$ ] that share a common factor greater than $1$ with $n$ .

Furthermore, we can define a second function, $g(n)$ , which characterizes the fraction of numbers that like a given number as follows: $g(n) = \frac{f(n)}{n}$ .

What we really want to know though, is, for any integer $2 ≤ k ≤ n$ , what is the maximum value of $g(k)$ ?

입력

The input consists of a single integer $n$ ( $2 ≤ n ≤ 10^{18}$ ), the value of $n$ for the input case.

출력

For the provided test case, output the result as a fraction, in lowest terms, in the form $p$ / $q$ where the greatest common divisor of $p$ and $q$ is 1.

예제2

예제 1
입력
```
10
```
예상 출력
```
2/3
```
예제 2
입력
```
100
```
예상 출력
```
11/15
```