시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 91 30 26 44.828%

문제

양의 정수 N이 있을 때, N을 나눌 수 없는 가장 작은 수 A를 찾을 수 있다. 예를 들어, 6은 4로 나누어 떨어지지 않으므로, A는 4가 된다.

이렇게 A를 찾은 다음, 그 수를 다시 N이라고 하고, 나눌 수 없는 가장 작은 수 A를 찾는 것을 계속해서 한다면, 결국에는 A는 2가 된다.

N이 2가 된다면, 더이상 찾지 않고 여기서 그만한다.

우리는 이런 성질을 이용해서 strength(N)을 위의 방법에서 나온 N의 수열의 길이로 정의할 수 있다.

예를 들어, N=6이라면 6, 4, 3, 2를 얻을 수 있으므로, strength(6) = 4가 된다.

두 양의 정수 A < B가 주어졌을 때, A와 B를 포함하여 그 사이에 있는 숫자의 힘의 합을 구하는 프로그램을 작성하시오.

strength(A) + strength(A+1) + ... + strength(B)

입력

첫째 줄에 두 정수 A와 B가 주어진다. (3 <= A < B < 1017)

출력

첫째 줄에 A와 B를 포함하여 그 사이에 있는 숫자의 합을 출력한다.

예제 입력 1

3 6

예제 출력 1

11
W3sicHJvYmxlbV9pZCI6IjI3OTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMmJcdWM3OTBcdWM3NTggXHVkNzk4IiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IE5cdWM3NzQgXHVjNzg4XHVjNzQ0IFx1YjU0YywgTlx1Yzc0NCBcdWIwOThcdWIyMGMgXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YzIxOCBBXHViOTdjIFx1Y2MzZVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCA2XHVjNzQwIDRcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0IFx1YjVhOFx1YzViNFx1YzljMFx1YzljMCBcdWM1NGFcdWM3M2NcdWJiYzBcdWI4NWMsIEFcdWIyOTQgNFx1YWMwMCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuPHA+XHJcblx0XHVjNzc0XHViODA3XHVhYzhjIEFcdWI5N2MgXHVjYzNlXHVjNzQwIFx1YjJlNFx1Yzc0YywgXHVhZGY4IFx1YzIxOFx1Yjk3YyBcdWIyZTRcdWMyZGMgTlx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWFjZTAsIFx1YjA5OFx1YjIwYyBcdWMyMTggXHVjNWM2XHViMjk0IFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVjMjE4IEFcdWI5N2MgXHVjYzNlXHViMjk0IFx1YWM4M1x1Yzc0NCBcdWFjYzRcdWMxOGRcdWQ1NzRcdWMxMWMgXHVkNTVjXHViMmU0XHViYTc0LCBcdWFjYjBcdWFkNmRcdWM1ZDBcdWIyOTQgQVx1YjI5NCAyXHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG48cD5cclxuXHROXHVjNzc0IDJcdWFjMDAgXHViNDFjXHViMmU0XHViYTc0LCBcdWIzNTRcdWM3NzRcdWMwYzEgXHVjYzNlXHVjOWMwIFx1YzU0YVx1YWNlMCBcdWM1ZWNcdWFlMzBcdWMxMWMgXHVhZGY4XHViOWNjXHVkNTVjXHViMmU0LjxcL3A+XHJcbjxwPlxyXG5cdFx1YzZiMFx1YjlhY1x1YjI5NCBcdWM3NzRcdWI3ZjAgXHVjMTMxXHVjOWM4XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBzdHJlbmd0aChOKVx1Yzc0NCBcdWM3MDRcdWM3NTggXHViYzI5XHViYzk1XHVjNWQwXHVjMTFjIFx1YjA5OFx1YzYyOCBOXHVjNzU4IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI4NWMgXHVjODE1XHVjNzU4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuPHA+XHJcblx0XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgTj02XHVjNzc0XHViNzdjXHViYTc0IDYsIDQsIDMsIDJcdWI5N2MgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJiYzBcdWI4NWMsIHN0cmVuZ3RoKDYpID0gNFx1YWMwMCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuPHA+XHJcblx0XHViNDUwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggQSAmbHQ7IEJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgQVx1YzY0MCBCXHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YzVlYyBcdWFkZjggXHVjMGFjXHVjNzc0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMyMmJcdWM3OTBcdWM3NTggXHVkNzk4XHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG48cD5cclxuXHRzdHJlbmd0aChBKSArIHN0cmVuZ3RoKEErMSkgKyAuLi4gKyBzdHJlbmd0aChCKTxcL3A+XHJcblxyXG5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjQ1MCBcdWM4MTVcdWMyMTggQVx1YzY0MCBCXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDMgJmx0Oz0gQSAmbHQ7IEIgJmx0OyAxMDxzdXA+MTc8XC9zdXA+KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgQVx1YzY0MCBCXHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YzVlYyBcdWFkZjggXHVjMGFjXHVjNzc0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMyMmJcdWM3OTBcdWM3NTggXHVkNTY5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyNzkzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU05BR0EiLCJkZXNjcmlwdGlvbiI6IjxwPkxldCB1cyBiZWdpbiB3aXRoIGEgcG9zaXRpdmUgaW50ZWdlciBOIGFuZCBmaW5kIHRoZSBzbWFsbGVzdCBwb3NpdGl2ZSBpbnRlZ2VyIHdoaWNoIGRvZXNuJiMzOTt0IGRpdmlkZSBOLiBJZiB3ZSByZXBlYXQgdGhlIHByb2NlZHVyZSB3aXRoIHRoZSByZXN1bHRpbmcgbnVtYmVyLCB0aGVuIGFnYWluIHdpdGggdGhlIG5ldyByZXN1bHQgYW5kIHNvIG9uLCB3ZSB3aWxsIGV2ZW50dWFsbHkgb2J0YWluIHRoZSBudW1iZXIgMiAodHdvKS4gTGV0IHVzIGRlZmluZSBzdHJlbmd0aChOKSBhcyB0aGUgbGVuZ3RoIG9mIHRoZSByZXN1bHRpbmcgc2VxdWVuY2UuPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBmb3IgTiA9IDYgd2Ugb2J0YWluIHRoZSBzZXF1ZW5jZSA2LCA0LCAzLCAyIHdoaWNoIGNvbnNpc3RzIG9mIDQgbnVtYmVycywgdGh1cyBzdHJlbmd0aCg2KSA9IDQuPFwvcD5cclxuXHJcbjxwPkdpdmVuIHR3byBwb3NpdGl2ZSBpbnRlZ2VycyBBICZsdDsgQiwgY2FsY3VsYXRlIHRoZSBzdW0gb2Ygc3RyZW5ndGhzIG9mIGFsbCBpbnRlZ2VycyBiZXR3ZWVuIEEgYW5kIEIgKGluY2x1c2l2ZSksIHRoYXQgaXMsPFwvcD5cclxuXHJcbjxwPnN0cmVuZ3RoKEEpICsgc3RyZW5ndGgoQSArIDEpICsgLi4uICsgc3RyZW5ndGgoQik8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBwb3NpdGl2ZSBpbnRlZ2VycywgQSBhbmQgQiAoMyAmbGU7IEEgJmx0OyBCICZsdDsgMTA8c3VwPjE3PFwvc3VwPikuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiB0aGUgcmVxdWVzdGVkIHN1bSBvZiBzdHJlbmd0aHMuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==