dreamoon_love_AA's blog

By dreamoon_love_AA, history, 2 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

»
2 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?

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

    hmm...far away.

  • »
    »
    2 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.

»
2 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)

  • »
    »
    2 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 $$$x, a, b$$$?

    • »
      »
      »
      2 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

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

        but there are some ugly cases such as $$$9\ /\ 8 * 7 = 9 * 7\ /\ 8$$$.

»
2 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$$$, $$$x/i$$$ will remain same ?

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

    Perhaps there is a $$$O(\ln x)$$$ or $$$O(\sqrt x)$$$ solution

  • »
    »
    2 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.

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

I have a half-solution to this problem:

pretends $$$x = ai + b,j = ci + d$$$($$$a,b,c,d$$$ is all integers and $$$b,d < i$$$)

Thus:

$$$x/i*j=aci+ad$$$

$$$x*j/i=\frac{aci^2+(ad+bc)i+bd}{i}$$$

$$$=aci+ad+bc+ \left \lfloor \frac{bd}{i} \right \rfloor$$$

So if $$$x*j/i$$$ equals to $$$x/i*j$$$,

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

or $$$j$$$ must be lower than $$$i$$$, and $$$j * (x\mod i) < i$$$

I think this can be done with $$$O(\ln x) + O(1)$$$ (but I didn't proof it)

Is this close to the jury answer?

(sorry for my poor English and my latex skills)

  • »
    »
    2 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 $$$x*j/i = x/i*j$$$, you need $$$bc = 0$$$ and $$$\left \lfloor \frac{bd}{i} \right \rfloor = 0$$$. For $$$bc = 0$$$, Case 1 is, either $$$b=0 ( x$$$%$$$i == 0 )$$$, which then automatically makes second condition true. Case 2 is, $$$c=0 (j < i \implies d = j)$$$, in which case second condition means $$$b*d < i$$$, or $$$b*j < i$$$, which means, when $$$j<i$$$ you need to count only when $$$b*j < i$$$. So totally, you need to count all $$$(i,j)$$$ where

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

    (OR)

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

    • »
      »
      »
      2 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)

    • »
      »
      »
      2 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

      • »
        »
        »
        »
        2 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 $$$i \le a$$$, we need to count number of $$$j$$$ such that $$$j<i$$$ ans $$$b*j<i$$$, since $$$b \ge 1$$$, the two conditions reduce to just one condition, $$$b*j<i$$$. So, given a particular $$$i$$$, number of $$$j$$$ is easily calculated as $$$\left \lfloor \frac{i}{b} \right \rfloor + 1$$$. 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 $$$i \in Factors(x)$$$, we have already counted $$$j$$$'s, so we need to subtract the AGP values corresponding to values of $$$i$$$ that are factors of $$$x$$$.

  • »
    »
    2 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 $$$j * (x \mod i) < i$$$" can merge to $$$j * (x \mod i) < i$$$?

    Then we may use this formula to do something.

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

»
2 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).