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
ogbonna_faith:
2015-05-31 21:33:54
hmmmm.. this problem is real difficult |
|
Kata:
2015-05-30 02:05:52
@utkarsha gaumat :
|
|
utkarsha gaumat:
2015-05-29 21:11:02
is the 6 7 test case answer correct?? |
|
Kata:
2015-05-29 14:47:20
@eightnoteight Thanks.
|
|
eightnoteight:
2015-05-29 13:34:21
@Kata
|
|
mehmetin:
2015-05-28 19:08:01
Good problem. It would be better if "tree_num" in the description is changed as "three_num", that would make more sense. |
|
harshabn808:
2015-05-28 00:21:46
@tjandra I am using Javascript. That makes it more interesting! :)
|
|
(Tjandra Satria Gunawan)(曾毅昆):
2015-05-28 00:01:03
@harshabn808: Time limit is OK, my unoptimized code easily got AC . Although it's hard or even impossible for slow languages like python or java. |
|
harshabn808:
2015-05-27 20:44:37
Are you sure about the time limit? |
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 |