Informatica Online Judge

  기약분수의 개수 [1594 / 063A]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 36   Total Tried : 39


The Champion of this Problem (C++) : gs19022 - 0ms / 217byte
My Best Submission (C++) : N/A

[koistudy.net (T. JH Park 2016)]

Background

(문제를 고쳐 보자~ ^^)

0에서 1사이(0, 1포함)으로 표현할 수 있는 기약분수에 대해서 생각해보자. (당연히 분자가 분모보다 같거나 적다.) 기약 분수는 분수로 표현된 분자와 분모가 1 이외의 공통된 약수로 더 이상 나누어 떨어지지 않는 형태가 된 것을 말한다.

여기서 분모를 N이하로 제한하고, N이 5일 경우 이러한 조건을 만족하는 모든 기약분수를 나타내면 다음과 같다.

0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1

1부터 160사이(1, 160포함)의 N값이 주어질 때, 위 조건을 만족하는 기약 분수의 수를 출력하는 프로그램을 작성하시오.

Input

하나의 정수 N이 주어진다.

Output

한 줄에 조건을 만족하는 기약분수의 수를 출력한다.

IO Example

입력
5

출력
11

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]