### Dream_Coder10's blog

By Dream_Coder10, history, 4 weeks ago,

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/ )?

# Thanks in advance

• -22

 » 4 weeks ago, # |   -11 the answer is simply printing n/k because 1 <= k <= n <= 1e9 so n/k easily fits in 1e9+7 lol
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   -8 Ok forget about fits/unfits...can u tell me why the test cases above is giving wa in moduler multiplecative inverse method?
•  » » » 4 weeks ago, # ^ |   +11 Change the while loop in the binary exponentiation function to:  while(n) { if(n%2) res=(res*a)%m; a=(a*a)%m, n/=2; } and your code will work as expected.BTW Melonade is wrong.
•  » » » » 4 weeks ago, # ^ |   0 It is giving output: 666666675 when n=11 & k=3 ; The correct output is 3
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by Dream_Coder10 (previous revision, new revision, compare).
 » 4 weeks ago, # | ← Rev. 2 →   0 You understood problem wrong. Right formulaanswer = $(\frac{n}{k})^k$BTW, your power-function is completely fine.
•  » » 4 weeks ago, # ^ |   0 Thanks a lot!!!!