Suppose there are two number n & k where 1 <= k <= n <= 1e9 . Now I have to calculate n/k (modulo 1e9 + 7)
==========================================================================================================================
My approach:
I used fermats little theorem to calculate moduler multiplecative inverse & then i printed n*(moduler multiplecitive inv.); But in this approach many test cases like "n=11,k=3" or "n=10 ,k=4" are not working properly & giving me wrong answer..
problem: ( https://paste.ubuntu.com/p/vgTZcHQ8Rv/ ) what I have to modify in this code ( https://paste.ubuntu.com/p/T2h9CsjpXx/ )?
the answer is simply printing n/k because 1 <= k <= n <= 1e9 so n/k easily fits in 1e9+7 lol
Ok forget about fits/unfits...can u tell me why the test cases above is giving wa in moduler multiplecative inverse method?
Change the while loop in the binary exponentiation function to:
and your code will work as expected.
BTW Melonade is wrong.
You understood problem wrong.
answer = $$$(\frac{n}{k})^k$$$
BTW, your power-function is completely fine.