TREENUM2 - The art of tree numbers
A number is called a tree_num while it can be partition into sum of some distinct powers of 3 with natural exponent. Example : 13 and 90 are tree_num because 13 = 32 + 31 + 30, 90 = 34 + 32.
Let $tree\_num(i)$ be the i-th largest tree_num.
Example : $tree\_num(1) = 1$, $tree\_num(2) = 3$, $tree\_num(5) = 10$, …
Let $$F(L, R) = \sum _{i = L}^R tree\_num(i)$$
Your task is to find F(L, R) with some given L, R.
Input
- First line : an integer T – number of testcases (1 ≤ T ≤ 100000)
- Next T lines : each line contains two number – L and R (1 ≤ L ≤ R ≤ 1018)
Output
- For each pair (L, R), output a line containing the value F(L, R). Since those values can be very large, just output them modulo 232
Example
Input: 5 1 3 3 3 4 5 6 7 2 5 Output: 8 4 19 25 26
hide comments
Sushovan Sen:
2021-11-12 12:53:45
Can anyone provide answer for
|
|
smso:
2020-02-05 08:53:21
precompute powers of 3 to beat TLE |
|
nadstratosfer:
2019-12-28 03:33:52
Enjoyed breaking it down. Glad I haven't solved all problems from this genre yet ;) |
|
i_own_you:
2016-07-15 22:48:52
@hm_98 nope, its 416707434. Nice question, accepted in O(T*logR) :) |
|
hm_98:
2016-07-03 13:50:08
Is output for L = 1 and R = 10^18 is 4184870227?
|
|
:.Mohib.::
2015-11-12 10:58:04
Finally did it....Thanks for really beautiful problem.....!! |
|
elise:
2015-09-05 02:55:14
Unsigned long long int can help a lot.
|
|
saurabh:
2015-07-31 22:39:48
Will java code not accept at all? I tried optimizing highly but to no avail. Am I wasting my time?
|
|
Shivaraj Lakka:
2015-07-31 08:50:39
I implemented it in O(T).. but constantly getting WA.!!!
|
|
goyal:
2015-07-21 17:01:18
nice que:) |
Added by: | Kata |
Date: | 2015-05-27 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 JS-MONKEY |
Resource: | TREENUM |