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
kartikeya :
2015-06-28 22:03:38
O(T*log(l)+log(r)) giving tle !!! Last edit: 2015-06-29 07:25:20 |
|
i_love_inu143:
2015-06-12 15:50:51
@mandrathax :
|
|
Kata:
2015-06-12 10:30:46
@ujzwt4it :
|
|
ujzwt4it:
2015-06-11 17:05:38
it doesn't work with the big input, what could be the problem?
|
|
Kata:
2015-06-11 16:36:15
@ujzwt4it :
|
|
ujzwt4it:
2015-06-11 15:11:09
I m getting NZEC though the code runs perfectly fine on ideone
|
|
Kata:
2015-06-05 15:41:40
Ameya Panse :
|
|
Ameya Panse:
2015-06-04 16:09:16
I'm getting TLE while the code is compiling. Is that how its supposed to work? |
|
Kata:
2015-06-03 07:44:13
@mandrathax :
|
|
mandrathax:
2015-06-03 01:11:28
This problem is AWESOME! Took me 4 TLEs and 2 WAs and went through 3 algos before getting AC.
|
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 |