신기한 수열 > 문제은행

본문 바로가기


문제은행

1101 : 신기한 수열

제한시간: 1000 ms    메모리제한: 128 MB
해결횟수: 5 회    시도횟수: 17 회   



다음과 같은 수열이 존재한다.
A(1) = 1, A(2) = 2
A(n) = A(1)~A(n-1)에서 사용 되지 않은 수 중 A(n-1)와의 공약수가 1보다 큰 수 중 가장 작은 수(n>2) 이 수열을 전개하면 다음과 같이 전개된다.

 

1, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15, 18, 14, 7, 21, 24, 16, 20, 22, 11, 33, 27

 

위의 수열은 다음과 같은 신기한 성질을 가지고 있다.
- 소수의 경우 오름차순으로 나타난다.
- 모든 정수가 수열 안에 나타난다.

 

임의의 숫자 n이 수열의 몇 번째 위치에 출력되는지 출력하는 프로그램을 작성하라.


첫 번째 줄에는 찾고자 하는 숫자 n(1≤n≤300,000)이 입력된다. 입력되는 숫자의 위치는 1,000,000 번째를 넘지 않는다고 가정한다.



찾고자 하는 숫자 n에 대해 다음과 같이 출력한다. The number n appears in location p. n은 찾고자 하는 숫자, p는 n의 수열 내 위치를 출력한다.


[Copy]
12
[Copy]
The number 12 appears in location 7.





East Central North America 2003, poj 1619

HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.