Блог пользователя Volodya333

Автор Volodya333, история, 6 лет назад, По-русски

Problem statement: Given n (n < 1e9) and equation n*x % (x-n) = 0. How many solution. Thank in advance, and sorry for my poor English.

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится +7 Проголосовать: не нравится

This solution is wrong the reason is stated in the replies.

I'm not 100% sure about my solution but here you go.

since n*x%(x — n) = 0 then nx — m(x — n) = 0.

nx — mx + mn = 0

moving things around we get

nx = mx — mn => mx — mn = nx turning this into a congruence

equation

we choose x as the mod

we get mx = mn (mod x) => mn = 0 (mod x)

since we know the constant is n then mn — nx = 0

by solving for m we get m = x

by substituting in the first equation we get

nx — x(x — n) = 0

nx — xx + xn = 0

2nx — xx = 0

by solving for n we get n = x/2.

If there is anything wrong please note it out

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

    we always have more than 1 answer, for example n = 6, x = 3 and n = 6, x = 4. The number of dividers of the number n is similar to the number of answers, but this is not true

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Yes you are right I think the problem is in this line:

      we get mx = mn (mod x) => mn = 0 (mod x)

      since we know the constant is n then mn — nx = 0

      I considered the constant to remain n but since one of the two numbers changed then this is wrong.

»
6 лет назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

Just use that n*x % (x-n) = n*(x-n + n) % (x-n) = (n*(x-n) + n^2) % (x-n) = n^2 % (x-n).

So the number of solutions is just the numbers of divisors of n2.