Survivor's blog

By Survivor, history, 2 years ago, In English,

link to spoj problem "blamoeba" i need help to complete this problem. i am stuck since last 2 days. solution was easy but i am not getting how to use modular inverse to calculate the final answer. answer — y/x = (m-1)*(m^n)/(m^n-1) (where m^n means m to the power n). how to calculate the gcd of numerator and denominator before using modulo ?
according to me the answer should be

x = (m^n-1)/gcd
y = (m-1)*(m^n)/gcd

help me to do this or correct me if i am doing something wrong
thanks in advance

 
 
 
 

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

Auto comment: topic has been updated by Survivor (previous revision, new revision, compare).

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

mn - 1 = (m - 1)(mn - 1 + mn - 2 + ... + m + 1)

So mn - 1 is always divisible by m - 1. And gcd(mn - 1, mn) = 1.

It can be calculated in time.

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

    thanks Um_nik sir
    got it AC
    link for AC solution for reference

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      how to find this problem is solved using
      x = (m^n-1)/gcd y = (m-1)*(m^n)/gcd
      this formula

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how to find this problem is solved using
    x = (m^n-1)/gcd y = (m-1)*(m^n)/gcd
    this formula

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to get the formulae for this x = (m^n-1)/gcd y = (m-1)*(m^n)/gcd thing !! i did't get it pls help ... i am also stuck since last few days. Survivor help.