When I use the normal iterative to compute the chebyshev and fermat’s little theorem for modular inverse,
I get wrong answer on the first subtask.
The given test cases are computed right tho, and yes, I need something better for when t is large
but could someone tell me what’s wrong in this code, at least for t <= 3?
There is other way to solve the question. Below is my approach:
We know e^ix = cos(x) + isin(x)
=> e^inx = cos(nx) + isin(nx)
We know cos(nx) + isin(nx) = (cos(x) + isin(x))^n
After computing we would have cos(nx) = real((cos(x) + isin(x))^n)
The multiplication can can be done in logn.
Here is the code: https://www.codechef.com/viewsolution/17348197
@manjuransari at one place u used the line
t_x = (xn_x)%mod - ((((y_xn_y_x)%mod)*diff)%mod)%mod;
cant we write it as t_x = [(xn_x)- ((((y_xn_y_x))*diff))]%mod;
i.e after multiplying all the values at last we are calculating mod
why using mod everytime as question clearly mentions you have to give FINAL result as ans%mod
why using mod every time will not affect our answer
@albert it is possible that multiplying the two values may result in integer overflow. Hence after multiplying two values take mod, and then multiply with third value.
i used binomial coefficients but iam getting wrong answer for some subtasks
If t=1, we return cos(tx)=(cos(x),0)and sin(tx)=(0,1);
Can anyone tell me why we are initializing sin(tx)=(0,1) ?
Can anyone please explain one example of this problem along with modular inverse calculation.
What is the problem if i do the following :
I find x as x = t* \theta - (int)(t* \theta/ \arctan(1)*8)* \theta
Is the problem due to floating point airthematic ?
Hello ‘d’ is opposite side right?‘l’ is Hypotenuse right?
came up with the exact formula of author . but didn’t have prior knowledge of Mexp…
it was a very good question …
What about simply using the 2 formulas-
cos (tx)= 2*{cos}^{2}(tx/2)-1 (even t)
and cos(tx)+cos(x)=2cos((t+1)x/2)*cos((t-1)x/2) (odd t)
No need for any complex as such formula if we use these.
yes…
this will be much time saver and also no dealing with irrational parts.
I used the exact same stuff as well XD. I mean, C’mon! All it needed was a little modification of fast exponentiation for my implementation :3
It is written in French but I guess you should be able to understand the basic idea by reading the equation.
So look for chapter: “Suite récurrente d’ordre p” on page: Suite récurrente linéaire — Wikipédia
NB: I did not find the same explanation in English.
you wont get ans in p/q form, even if u try to use fractions in python, you’ll have to round your cos(tx), in this case you’ll get wrong ans because precision will be different.
@siddharthp538 why not do mod 360 or 2*PI depending whether you are using degrees or radians, and then t will be a very small value and precision will be saved right ?
Actually this happened with me during the contest, i was getting cos(60) as 0.4999999999999999 and using Fraction if u convert it in p/q form then p comes as 4503599627370495 and q comes as 9007199254740992. p*(q^-1) comes out to be 879237148. It makes a huge diff to our ans. Actually if u do mod 360 still values will be rounded. It can give us wa.
This is identical to the tester’s solution, only interpreted as complex numbers.