Dream_Coder10's blog

By Dream_Coder10, history, 3 years ago, In English

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

  • Vote: I like it
  • -22
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it -11 Vote: I do not like it

the answer is simply printing n/k because 1 <= k <= n <= 1e9 so n/k easily fits in 1e9+7 lol

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it -8 Vote: I do not like it

    Ok forget about fits/unfits...can u tell me why the test cases above is giving wa in moduler multiplecative inverse method?

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      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.

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

You understood problem wrong.

Right formula

BTW, your power-function is completely fine.