시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB1241028582.524%

문제

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

\(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

1 34

예제 출력 1

561
W3sicHJvYmxlbV9pZCI6IjkyNzIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVjNTQ0XHVjNzc0XHViNTE0XHVjNWI0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNTQ0XHViNGU0XHVjNWQwXHVhYzhjIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHViYjM4XHVjODFjXHViOTdjIFx1YjBjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XFwoMSBcXGxlIG5fMSAmbHQ7IG5fMiBcXGxlIDEwXjRcXClcdWI5N2MgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YjQ1MCBcdWM4MTVcdWMyMTggXFwobl8xXFwpXHVhY2ZjIFxcKG5fMlxcKVx1YWMwMCBcdWM3ODhcdWIyZTQuIFx1ZDU2OFx1YzIxOCBcXChwOlxcbWF0aGJie059XiogXFxyaWdodGFycm93IFxcbWF0aGJie059XipcXCksIFxcKHAobikgPSAyXm5cXCksIFxcKFxcZm9yYWxsIG4gXFxpbiAmbmJzcDsgXFxtYXRoYmJ7Tn1eKlxcKSBcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0IFx1YjJlNFx1Yzc0YyBcdWM5ZDFcdWQ1NjlcdWM3NDQgXHVjODE1XHVjNzU4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIChcXChcXG1hdGhiYntOfV4qXFwpXHViMjk0IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NTggXHVjOWQxXHVkNTY5XHVjNzc0XHViMmU0KTxcL3A+XHJcblxyXG48cD5cXFtTKG5fMSxuXzIpPVxcbGVmdFxceyBwKHAobikpKzEgfG5fMSBcXGxlIG4gXFxsZSBuXzIgJm5ic3A7XFxyaWdodFxcfSBcXF08XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWMzMGRcdWM3NTggXHVjOWQxXHVkNTY5XHViM2M0IFx1YzgxNVx1Yzc1OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cXFtUKG5fMSxuXzIpPVxcbGVmdFxceyAobV8xLG1fMikgfCBtXzEsbV8yIFxcaW4gJm5ic3A7UyhuXzEsbl8yKSwgbV8xICZsdDsgbV8yICZuYnNwO1xccmlnaHRcXH0gXFxdPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YzgxYyBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YzJkZFx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XFxbUihuXzEsbl8yKT0gXFxzdW1feyhtXzEsbV8yKSBcXGluIFQobl8xLG5fMil9e2djZChtXzEsbV8yKX1cXF08XC9wPlxyXG5cclxuPHA+XFwoZ2NkKG1fMSxtXzIpXFwpXHViMjk0IFxcKG1fMVxcKVx1YzY0MCBcXChtXzJcXClcdWM3NTggXHVjZDVjXHViMzAwIFx1YWNmNVx1YzU3ZFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XFwobl8xXFwpXHVhY2ZjIFxcKG5fMlxcKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcXChSKG5fMSxuXzIpXFwpXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWI0NTAgXHVjODE1XHVjMjE4IFxcKG5fMVxcKVx1YWNmYyBcXChuXzJcXClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXFwoUihuXzEsbl8yKVxcKVx1Yzc1OCBcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjkyNzIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJBbiBJZGVhIG9mIE1yLiBBIiwiZGVzY3JpcHRpb24iOiI8cD5Nci4gQSBwcm9wb3NlcyB0byBoaXMgc29uIHRoZSBmb2xsb3dpbmcgcHJvYmxlbTo8XC9wPlxyXG5cclxuPHA+JnF1b3Q7Q29uc2lkZXIgdG93IGludGVnZXJzIFxcKG5fMVxcKSBhbmQgXFwobl8yXFwpIHN1Y2ggdGhhdCBcXCgxIFxcbGUgbl8xICZsdDsgbl8yIFxcbGUgMTBeNFxcKS4gVXNpbmcgdGhlIGZ1bmN0aW9uIFxcKHA6XFxtYXRoYmJ7Tn1eKiBcXHJpZ2h0YXJyb3cgXFxtYXRoYmJ7Tn1eKlxcKSwgXFwocChuKSA9IDJeblxcKSwgXFwoXFxmb3JhbGwgbiBcXGluICZuYnNwOyBcXG1hdGhiYntOfV4qXFwpICh3aGVyZSBcXChcXG1hdGhiYntOfV4qXFwpIGlzIHRoZSBzZXQgb2YgcG9zaXRpdmUgaW50ZWdlcnMpIHdlIGRlZmluZSB0aGUgc2V0PFwvcD5cclxuXHJcbjxwPlxcW1Mobl8xLG5fMik9XFxsZWZ0XFx7IHAocChuKSkrMSB8bl8xIFxcbGUgbiBcXGxlIG5fMiAmbmJzcDtcXHJpZ2h0XFx9IFxcXTxcL3A+XHJcblxyXG48cD5XZSBhbHNvIGRlZmluZSBhIHNldCBvZiBwYWlycyBhcyBmb2xsb3dzOiZuYnNwOzxcL3A+XHJcblxyXG48cD5cXFtUKG5fMSxuXzIpPVxcbGVmdFxceyAobV8xLG1fMikgfCBtXzEsbV8yIFxcaW4gJm5ic3A7UyhuXzEsbl8yKSwgbV8xICZsdDsgbV8yICZuYnNwO1xccmlnaHRcXH0gXFxdPFwvcD5cclxuXHJcbjxwPkNvbnNpZGVyIHRoZSBmb3JtdWxhOiZuYnNwOzxcL3A+XHJcblxyXG48cD5cXFtSKG5fMSxuXzIpPSBcXHN1bV97KG1fMSxtXzIpIFxcaW4gVChuXzEsbl8yKX17Z2NkKG1fMSxtXzIpfVxcXTxcL3A+XHJcblxyXG48cD53aGVyZSBcXChnY2QobV8xLG1fMilcXCkgaXMgdGhlIGdyZWF0ZXN0IGNvbW1vbiBkaXZpc29yIG9mIFxcKG1fMVxcKSBhbmQgXFwobV8yXFwpLiBUaGUgcHJvYmxlbSBhc2sgdG8gZmluZCB0aGUgbnVtYmVyIFxcKFIobl8xLG5fMilcXCkuJnF1b3Q7PFwvcD5cclxuXHJcbjxwPlNvbHZlIHRoZSBwcm9ibGVtIHByb3Bvc2VkIGJ5IE1yLiBBLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGZpbGUgY29uc2lzdHMgb2YgYSBzaW5nbGUgbGluZSBoYXZpbmcgdGhlIHZhbHVlcyBmb3IgXFwobl8xXFwpIGFuZCBcXChuXzJcXCksIHNlcGFyYXRlZCBieSBleGFjdGx5IG9uZSBzcGFjZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0LCB0aGUgcmVzdWx0IHdpbGwgYmUgd3JpdHRlbiB0byBzdGFuZGFyZCBvdXRwdXQgYW5kIGNvbnNpc3RzIG9mIHRoZSB2YWx1ZSBvZiBcXChSKG5fMSxuXzIpXFwpLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Europe > Southeastern European Regional Contest > SEERC 2013 J번