Please Help , How to solve this question related to recursion?

general
1

https://mycode.prepbytes.com/problems/recursion/MAGSUM

2

Hey @k_purushottam :wave: ,
I solved this using Bit manipulation but it’s kinda tricky.
I first founded all the sequence till (m+1).
1
1+x
1+x+x^2
1+x+x^2+x^3
and so…on
till (m+1).
and I took prefix sum of this(whole (m+1) sequence sum).
but as we only required m sequence we remove (t - (m+1)) sequcence.
that’s it , removing is like taking rem = (t-(m+1)) and check if ith bit is set in rem. If bit is set then we want that to be removed from whoever has that bit to be set in rem.
Here is my code I suggest you to use pen and paper on how loops work you will soon get that.

for _ in range (int(input())) :
    x,m,n = list(map(int,input().split()))
    b = [1]
    t = 1
    tot = 1
    y = x
    p = x
    
    while (t <= (m+1)) : #try pen and paper for this loop to check how this is working
        tot += tot*y
        tot %= n
        b.append(tot) #list is pushing all prefix sums
        y*=p
        y%=n
        p = y
        t*=2
    ans = b[-1]
    rem = t - m - 1
    bt = bin(rem)[2:][::-1]
    
    for i in range (len(bt)) :
        if (bt[i] == '0') :
            continue
        t -= pow(2,i)
        ans += n
        val = pow(x,t,n)
        ans -= (val*b[i])%n
        ans %= n

    print(ans)
1 Like
3

Thanks a lot … :smiley: I will study you solution. It is well written actually these days have my semester exam so it took me a lot time to respond.