dreamoon_love_AA's blog

Why x * i / j is not equal to x / j * i ?
By dreamoon_love_AA, history, 5 years ago, In English

Hi, all.

I found a magic thing that $$$x\ /\ i * j$$$ is not always equal to $$$x * j\ /\ i$$$! For example, when $$$x = 12, i = 9, j = 6$$$, then $$$x\ /\ i * j = 6$$$ but $$$x * j\ /\ i = 8$$$. The fact surprised me.

Now, given three positive number $$$x$$$, $$$a$$$, $$$b$$$, I wonder how may pair of $$$(i,j)$$$ satisfy $$$x\ /\ i * j = x * j\ /\ i$$$ and $$$1 \le i \le a$$$ and $$$1 \le j \le b$$$?

I hope I can solve about $$$20$$$ tests which satisfy $$$1 \le x,a,b \le 10^9$$$ in 1 second. Can you help me?

PS. This is a problem that I give in some local contest. I feel it's interesting and share it here.

PS2. I think it's a math problem instead of programing problem.

  • Vote: I like it
  • +89
  • Vote: I do not like it

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

mx = max( a, b )

mn = min( a, b )

div = [ divisors of x <= mx ]

ans = div.len * mn

Is this close to the correct solution?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    hmm...far away.

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

    Only counting divisors won't do. Because even if there's a loss on both sides, the equation may hold. For example, x=15,i=7,j=3.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

That's because of '/' => for example you have 12 / 9 = 1, but 12 / 9 = 1.(3)

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +43 Vote: I do not like it

    WoW! programming language is so different from math! But I'm a curious man, I wonder know more! Can you tell me there are how much pair of $$$(i,j)$$$ such that $$$x\ /\ i * j = x * j\ /\ i$$$ and $$$1 \le i \le a$$$ and $$$1 \le j \le b$$$ when given

    Unable to parse markup [type=CF_MATHJAX]

    ?
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, that's easy : you should find all divisors of common divisors of x and i

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        but there are some ugly cases such as

        Unable to parse markup [type=CF_MATHJAX]

        .
        → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

By the second point, PS2, do you mean there is a $$$O(1)$$$ solution, or just some mathematical application. Maybe you have to use the fact that for each $$$i$$$ between two consecutive factors of $$$x$$$,

Unable to parse markup [type=CF_MATHJAX]

will remain same ?
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Perhaps there is a

    Unable to parse markup [type=CF_MATHJAX]

    or $$$O(\sqrt x)$$$ solution
    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I mean the complexity proving part is farther harder than algorithm part. Some people can get AC on this problem, but seldom can prove the method is good enough.

    → Reply
»
5 years ago, # |
← Rev. 5   Vote: I like it +1 Vote: I do not like it

I have a half-solution to this problem:

pretends

Unable to parse markup [type=CF_MATHJAX]

($$$a,b,c,d$$$ is all integers and

Unable to parse markup [type=CF_MATHJAX]

)

Thus:

Unable to parse markup [type=CF_MATHJAX]

Unable to parse markup [type=CF_MATHJAX]

Unable to parse markup [type=CF_MATHJAX]

So if

Unable to parse markup [type=CF_MATHJAX]

equals to

Unable to parse markup [type=CF_MATHJAX]

,

$$$x$$$ must be a multiple of $$$i$$$,

or $$$j$$$ must be lower than $$$i$$$, and

Unable to parse markup [type=CF_MATHJAX]

I think this can be done with

Unable to parse markup [type=CF_MATHJAX]

(but I didn't proof it)

Is this close to the jury answer?

(sorry for my poor English and my latex skills)

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    I don't think you're considering the correct possibilities. For

    Unable to parse markup [type=CF_MATHJAX]

    , you need

    Unable to parse markup [type=CF_MATHJAX]

    and

    Unable to parse markup [type=CF_MATHJAX]

    . For

    Unable to parse markup [type=CF_MATHJAX]

    , Case 1 is, either

    Unable to parse markup [type=CF_MATHJAX]

    %

    Unable to parse markup [type=CF_MATHJAX]

    , which then automatically makes second condition true. Case 2 is,

    Unable to parse markup [type=CF_MATHJAX]

    , in which case second condition means

    Unable to parse markup [type=CF_MATHJAX]

    , or

    Unable to parse markup [type=CF_MATHJAX]

    , which means, when $$$j<i$$$ you need to count only when

    Unable to parse markup [type=CF_MATHJAX]

    . So totally, you need to count all $$$(i,j)$$$ where

    1). $$$i$$$ divides $$$x$$$ ( $$$j$$$ can be any ).

    (OR)

    2). $$$j<i$$$ and

    Unable to parse markup [type=CF_MATHJAX]

    .
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh yes.

      At first I forget a possibility of $$$c = 0$$$ (because of my poor logical mind)

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

      So I still don't know whether there's more possibilities to this problem, and I don't think this is the correct solution to a problem

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

        I think it's correct, there don't seem to be any awkward assumptions and/or any logical gaps in your argument, except considering all possibilities. Also, first part can be done in $$$O(\sqrt{x})$$$ and second should be possible in $$$O(1)$$$ time by following

        For each

        Unable to parse markup [type=CF_MATHJAX]

        , we need to count number of $$$j$$$ such that $$$j<i$$$ ans

        Unable to parse markup [type=CF_MATHJAX]

        , since $$$b \ge 1$$$, the two conditions reduce to just one condition,

        Unable to parse markup [type=CF_MATHJAX]

        . So, given a particular $$$i$$$, number of $$$j$$$ is easily calculated as

        Unable to parse markup [type=CF_MATHJAX]

        . Summing this over all $$$i$$$ between 1 and a gives something like an AGP. But the point to note here is that, we have added these $$$j$$$ for every $$$1 \le i \le a$$$, but for

        Unable to parse markup [type=CF_MATHJAX]

        , we have already counted $$$j$$$'s, so we need to subtract the AGP values corresponding to values of $$$i$$$ that are factors of $$$x$$$.
        → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it

    Do you notice that "$$$x$$$ must be a multiple of $$$i$$$"or "$$$j < i$$$ and

    Unable to parse markup [type=CF_MATHJAX]

    " can merge to

    Unable to parse markup [type=CF_MATHJAX]

    ?

    Then we may use this formula to do something.

    Congratulation! This is the first part of my attempted solution.

    → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

(x — x / i) * j < i

x * j < i + x / i

Iterate by all x / i, then we should be able to calculate the number of pairs (i, j) in O(1).

→ Reply