시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 105 | 49 | 45 | 51.136% |
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.
10
2/3
100
11/15
ICPC > Regionals > North America > North America Qualification Contest > ICPC North America Qualifier 2021 C번