[BOJ 9272] 상근이의 아이디어
View as PDF
Submit solution
Assembly, Awk, C, C++, Java, Pascal, Perl, Python, Sed, Text
Points:
2
Time limit:
2.0s
Memory limit:
128M
Problem types
Allowed languages
상근이는 아들에게 다음과 같은 문제를 냈다.
(1 \le n_1 < n_2 \le 10^4)를 만족하는 두 정수 (n_1)과 (n_2)가 있다. 함수 (p:\mathbb{N}^ \rightarrow \mathbb{N}^), (p(n) = 2^n), (\forall n \in \mathbb{N}^) 을 이용해 다음 집합을 정의할 수 있다. ((\mathbb{N}^)는 양의 정수의 집합이다)
[S(n_1,n_2)=\left{ p(p(n))+1 |n_1 \le n \le n_2 \right} ]
다음과 같은 쌍의 집합도 정의할 수 있다.
[T(n_1,n_2)=\left{ (m_1,m_2) | m_1,m_2 \in S(n_1,n_2), m_1 < m_2 \right} ]
이제 다음과 같은 식을 만들 수 있다.
[R(n_1,n_2)= \sum_{(m_1,m_2) \in T(n_1,n_2)}{gcd(m_1,m_2)}]
(gcd(m_1,m_2))는 (m_1)와 (m_2)의 최대 공약수이다.
(n_1)과 (n_2)가 주어졌을 때, (R(n_1,n_2))를 구하는 프로그램을 작성하시오.
입력 형식
첫째 줄에 두 정수 (n_1)과 (n_2)가 주어진다.
출력 형식
첫째 줄에 (R(n_1,n_2))의 값을 출력한다.
예제 입력
1 34
예제 출력
561
Comments