Firstly i came up with this solution: https://mirror.codeforces.com/contest/1542/submission/121218884 I think it's O(n) in worst cases, and i got TLE. But shouldn't O(n) be sufficient for these constraints?
After the contest I also updated a O(logn) solution, and its similar to others that i saw submitted, but its getting TLE too: https://mirror.codeforces.com/contest/1542/submission/121269280
What am I missing here?
I didn't think much but Im certain that you should make p long long. Its possible for it to keep overflowing and doing a lot of interactions.
Thanks, it worked for the O(logn) solution, but the solution that i submitted in the contest is still getting TLE even if I #define int long long: https://mirror.codeforces.com/contest/1542/submission/121270476
Why do you think this is happening? O(n) isn't fast enough?
its very far from linear actually
If $$$a$$$ is $$$10^9-1$$$ and $$$n$$$ is $$$10^9$$$,first $$$p$$$ will multipliy by $$$a$$$ and then $$$p$$$ is $$$10^9-1$$$,second $$$p$$$ will multiply by $$$a$$$ again and $$$p$$$ will be more than $$$\text{INT_MAX}$$$.It will be very likely that $$$p$$$ overflows and make it less than or equal to $$$n$$$,so this code will keep running and you will get TLE.
Thanks, i get it in O(logn) sol, but do you know why
isn't working? isn't it linear?
this
You can't simulate the process of substracting b,it is very likely to get TLE,too.And the solution isn't substracting or dividing,it is adding and multipling.
Sorry,I can see your picture that you post.
this submission
Let $$$x=1$$$.
If you add $$$b$$$ to $$$x$$$ first,and then multiply $$$x$$$ by $$$a$$$.In fact, it is equivalent to multiply $$$x$$$ by $$$a$$$ and add $$$b$$$ to $$$x$$$ for $$$a$$$ times.So you should multiply first and add,then you can strictly get $$$O(\log n)$$$
Let $$$a=10^9,b=1,n=10^9-1$$$,when you take this data to your code and run it again, the program will continue to decrease by $$$1$$$, so that your code will be linear and will burst.