### dreamoon_love_AA's blog

By dreamoon_love_AA, history, 2 years ago,

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.

• +89

 » 2 years ago, # | ← Rev. 2 →   0 mx = max( a, b )mn = min( a, b )div = [ divisors of x <= mx ]ans = div.len * mnIs this close to the correct solution?
•  » » 2 years ago, # ^ |   +21 hmm...far away.
•  » » 2 years ago, # ^ |   +3 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, # |   0 That's because of '/' => for example you have 12 / 9 = 1, but 12 / 9 = 1.(3)
•  » » 2 years ago, # ^ |   +43 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, # ^ |   0 Yes, that's easy : you should find all divisors of common divisors of x and i
•  » » » » 2 years ago, # ^ |   0 but there are some ugly cases such as $9\ /\ 8 * 7 = 9 * 7\ /\ 8$.
 » 2 years ago, # | ← Rev. 2 →   0 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, # ^ |   0 Perhaps there is a $O(\ln x)$ or $O(\sqrt x)$ solution
•  » » 2 years ago, # ^ |   0 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 →   +1 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 →   0 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 •  » » » 2 years ago, # ^ | 0 Oh yes.At first I forget a possibility of$c = 0$(because of my poor logical mind) •  » » » 2 years ago, # ^ | ← Rev. 2 → 0 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 → 0 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 followingFor each$i \le a$, we need to count number of$j$such that$j
•  » » 2 years ago, # ^ | ← Rev. 3 →   +1 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 →   +1 (x — x / i) * j < ix * j < i + x / iIterate by all x / i, then we should be able to calculate the number of pairs (i, j) in O(1).
•  » » 2 years ago, # ^ |   +2 not x-x/i, x-(x/i)*i