[BOJ 9272] 상근이의 아이디어

View as PDF

Submit solution

Points: 2
Time limit: 2.0s
Memory limit: 128M

Problem types
Allowed languages
Assembly, Awk, C, C++, Java, Pascal, Perl, Python, Sed, Text

상근이는 아들에게 다음과 같은 문제를 냈다.

(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

There are no comments at the moment.