Problem Link
contest link
practice link
PREREQUISITES
Beatty Theorem
Solution
The question is based on Beatty Theorem
Using the above theorem , for given irrational number alpha , you can calculate the the sum of first N terms of beatty sequence in O(log(N)) as follows :
Let S(α,n)=∑(k=1 → n) ⌊αk⌋ for α some irrational positive number.
if α≥2 we let β = α −⌊α⌋ + 1 and you get
S(α,n) = S(β,n) + (⌊α⌋ - 1)∑(k=1 → n)k = S(β,n) + (⌊α⌋ - 1) * n(n+1)/2
else if 1<α<2
if β satisfies α^−1 + β^−1 = 1 and m = ⌊αn⌋ , then
S(α,n)+S(β,⌊m/β⌋) =∑(k=1 → m) = m(m+1)/2
Also, ⌊m/β⌋ = m − ⌈m/α⌉ = m−n = ⌊(α−1)n⌋.
Then, letting n′=⌊(α−1)n⌋ you have
S(α,n)=(n+n′)(n+n′+1)/2−S(β,n′)
This gives us a solution for O(log(N))
A naive implementation of the above would only fetch 50 points and would get TLE on the rest . To secure complete 100 few things need to be kept in mind :
-
Integer Division is very very faster as comparative to decimal division , especially when numbers are of of order of 10^4000 .
-
You convert a decimal into integer as follows :
if u want to preserve M digits of a decimal number e , then
new_e = e * ( 10 ** M )
thus e - 1 would change to new_e - 10**M , similarly for addition
for division a/b will change to ( new_a * 10**M ) // new_b
to find floor(e) you can use new_e // 10**M
These are the operations that need to performed with decimal numbers for this question .
This will make your code fast , but not enough , we need to do better .
- Division and multiplication by a power of 2 can be done a lot faster .
thus new_e = e << N , where N is some number that will preserve enough digits of e ,( for given question N = 26600 would suffice )
A careful implementation with above optimizations would get AC .
My AC solution
Note: You would have to calculate the value of e online . There many ways to do so , refer link
One of the fast ways to do so is link