OJ Board

Yes, now I know for sure, this is not greedy. And to optimize the dp complexity, you need Knuth optimization(may be quadrangle inequality)

I think this is a dp problem. Though the straight-forward dp is n^3, it requires a n^2 version to get accepted. I haven't got accepted yet, though. But greedy should be incorrect. I don't have any cases right now, may be someone else will post some.

Can I have some I/O for this problem?

Actually I made too silly a mistake. In the power function, I took the argument as power(Matrix M, int n) but n can be long long. This caused a loop in the function and hence the TLE.

I am getting TLE in this problem. My solution has complexity log(n). But it still gets TLE. I would like some I/O. Though I have tested my program myself for some large inputs near 10^15. I am not posting the code at this stage. At last accepted. I did a funny mistake. In the function of Matrix expo...

Can anyone explain me about the problem? You are given a, c, you have to find the minimum b such that Lcm(a,b)=c. So c must be divisible by a, otherwise there is no such b. Now, for a prime p dividing a or b, Lcm(a,b)= product of p^{max(e1, e2)} where e1=power of p in prime factorization of a, e2 =...

There is a solution except matrix exponentiation. Say, you want to find d*(1+b+b^2+b^3+b^4)%M. What can you do? You don't need d at first. Let f(b,n,M) gives you the remainder. We can write it as 1+b+b^2+b^3+b^4=1+b+b^2(1+b)+b^4=(1+b)*(1+b^2)+b^4 f(b,n,m)=f(b,n/2,m)*(1+b^{n/2})+b^n if n even and f(b...

easy if you know something related to nim. Like bogus nim or staircase nim. But you have to sense it properly.

Posted an ac code. So deleted.