Conjecture
TopCoder SRM 785
Time Limit: 0.2s, Memory Limit: 64MiB
Преди много време Ели беше чула за хипотезата на Колац, но явно не я помни добре. Начинът, по който я помни, е следният:
Например, нека видим какво става ако започнем с X = 42. Числото е четно, затова го делим на 2, получавайки 21. 21 е нечетно, затова добавяме 3 и получаваме 24. 24 е четно, затова го делим на 2, получавайки 12. 12 също е четно, затова делим и него на 2 и получаваме 6. 6 все още е четно, затова делим и него на 2 и получаваме 3. 3 вече е нечетно, затова добавяме 3 към него, получавайки 6, което е и първото повторено число. Така резултатът за X = 42 е 6. Ели ви е помолила да намерите сумата от резултатите за всички стартови числа между две дадени от нея цели числа L и R (тоест, за всички L ≤ X ≤ R).
- Започнете с някакво цяло положително число X.
- Ако числото, което имате, е четно, го разделете на две.
- Ако числото, което имате, е нечетно го умножете по едно и добавете три (ефективно просто добавяйки три).
- Продължете да правите това докато стигнете до число, което вече сте имали.
Например, нека видим какво става ако започнем с X = 42. Числото е четно, затова го делим на 2, получавайки 21. 21 е нечетно, затова добавяме 3 и получаваме 24. 24 е четно, затова го делим на 2, получавайки 12. 12 също е четно, затова делим и него на 2 и получаваме 6. 6 все още е четно, затова делим и него на 2 и получаваме 3. 3 вече е нечетно, затова добавяме 3 към него, получавайки 6, което е и първото повторено число. Така резултатът за X = 42 е 6. Ели ви е помолила да намерите сумата от резултатите за всички стартови числа между две дадени от нея цели числа L и R (тоест, за всички L ≤ X ≤ R).
Вход
На единствен ред на стандартния вход ще бъдат зададени целите числа L и R.
Изход
На единствен ред на стандартния изход изведете едно цяло число – желаната сума.
Ограничения
- 1 ≤ L ≤ R ≤ 1,000,000,000
Примерен Вход | Примерен Изход |
---|---|
13 17 | 22 |
42 1337 | 6048 |
42666 133742 | 425026 |
В първия пример резултатите за числата в интервала [13, 17] са: 4, 4, 6, 4, 4.
Тяхната сума е 4 + 4 + 6 + 4 + 4 = 22.