시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB4501209832.997%

문제

양의 정수 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

예제 입력 2

100 200

예제 출력 2

262
W3sicHJvYmxlbV9pZCI6IjI3OTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMmJcdWM3OTBcdWM3NTggXHVkNzk4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IE5cdWM3NzQgXHVjNzg4XHVjNzQ0IFx1YjU0YywgTlx1Yzc0NCBcdWIwOThcdWIyMGMgXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YzIxOCBBXHViOTdjIFx1Y2MzZVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCA2XHVjNzQwIDRcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0IFx1YjVhOFx1YzViNFx1YzljMFx1YzljMCBcdWM1NGFcdWM3M2NcdWJiYzBcdWI4NWMsIEFcdWIyOTQgNFx1YWMwMCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YjgwN1x1YWM4YyBBXHViOTdjIFx1Y2MzZVx1Yzc0MCBcdWIyZTRcdWM3NGMsIFx1YWRmOCBcdWMyMThcdWI5N2MgXHViMmU0XHVjMmRjIE5cdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTU4XHVhY2UwLCBcdWIwOThcdWIyMGMgXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YzIxOCBBXHViOTdjIFx1Y2MzZVx1YjI5NCBcdWFjODNcdWM3NDQgXHVhY2M0XHVjMThkXHVkNTc0XHVjMTFjIFx1ZDU1Y1x1YjJlNFx1YmE3NCwgXHVhY2IwXHVhZDZkXHVjNWQwXHViMjk0IEFcdWIyOTQgMlx1YWMwMCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPk5cdWM3NzQgMlx1YWMwMCBcdWI0MWNcdWIyZTRcdWJhNzQsIFx1YjM1NFx1Yzc3NFx1YzBjMSBcdWNjM2VcdWM5YzAgXHVjNTRhXHVhY2UwIFx1YzVlY1x1YWUzMFx1YzExYyBcdWFkZjhcdWI5Y2NcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzZiMFx1YjlhY1x1YjI5NCBcdWM3NzRcdWI3ZjAgXHVjMTMxXHVjOWM4XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBzdHJlbmd0aChOKVx1Yzc0NCBcdWM3MDRcdWM3NTggXHViYzI5XHViYzk1XHVjNWQwXHVjMTFjIFx1YjA5OFx1YzYyOCBOXHVjNzU4IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI4NWMgXHVjODE1XHVjNzU4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIE49Nlx1Yzc3NFx1Yjc3Y1x1YmE3NCA2LCA0LCAzLCAyXHViOTdjIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYmMwXHViODVjLCBzdHJlbmd0aCg2KSA9IDRcdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCBBICZsdDsgQlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBBXHVjNjQwIEJcdWI5N2MgXHVkM2VjXHVkNTY4XHVkNTU4XHVjNWVjIFx1YWRmOCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzIyYlx1Yzc5MFx1Yzc1OCBcdWQ3OThcdWM3NTggXHVkNTY5XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5zdHJlbmd0aChBKSArIHN0cmVuZ3RoKEErMSkgKyAuLi4gKyBzdHJlbmd0aChCKTxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWI0NTAgXHVjODE1XHVjMjE4IEFcdWM2NDAgQlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgzICZsdDs9IEEgJmx0OyBCICZsdDsgMTA8c3VwPjE3PFwvc3VwPik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIEFcdWM2NDAgQlx1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NThcdWM1ZWMgXHVhZGY4IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwXHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjc5MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNOQUdBIiwiZGVzY3JpcHRpb24iOiI8cD5MZXQgdXMgYmVnaW4gd2l0aCBhIHBvc2l0aXZlIGludGVnZXIgTiBhbmQgZmluZCB0aGUgc21hbGxlc3QgcG9zaXRpdmUgaW50ZWdlciB3aGljaCBkb2VzbiYjMzk7dCBkaXZpZGUgTi4gSWYgd2UgcmVwZWF0IHRoZSBwcm9jZWR1cmUgd2l0aCB0aGUgcmVzdWx0aW5nIG51bWJlciwgdGhlbiBhZ2FpbiB3aXRoIHRoZSBuZXcgcmVzdWx0IGFuZCBzbyBvbiwgd2Ugd2lsbCBldmVudHVhbGx5IG9idGFpbiB0aGUgbnVtYmVyIDIgKHR3bykuIExldCB1cyBkZWZpbmUgc3RyZW5ndGgoTikgYXMgdGhlIGxlbmd0aCBvZiB0aGUgcmVzdWx0aW5nIHNlcXVlbmNlLjxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgZm9yIE4gPSA2IHdlIG9idGFpbiB0aGUgc2VxdWVuY2UgNiwgNCwgMywgMiB3aGljaCBjb25zaXN0cyBvZiA0IG51bWJlcnMsIHRodXMgc3RyZW5ndGgoNikgPSA0LjxcL3A+XHJcblxyXG48cD5HaXZlbiB0d28gcG9zaXRpdmUgaW50ZWdlcnMgQSAmbHQ7IEIsIGNhbGN1bGF0ZSB0aGUgc3VtIG9mIHN0cmVuZ3RocyBvZiBhbGwgaW50ZWdlcnMgYmV0d2VlbiBBIGFuZCBCIChpbmNsdXNpdmUpLCB0aGF0IGlzLDxcL3A+XHJcblxyXG48cD5zdHJlbmd0aChBKSArIHN0cmVuZ3RoKEEgKyAxKSArIC4uLiArIHN0cmVuZ3RoKEIpPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gcG9zaXRpdmUgaW50ZWdlcnMsIEEgYW5kIEIgKDMgJmxlOyBBICZsdDsgQiAmbHQ7IDEwPHN1cD4xNzxcL3N1cD4pLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gdGhlIHJlcXVlc3RlZCBzdW0gb2Ygc3RyZW5ndGhzLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #1 5번