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.
mx = max( a, b )
mn = min( a, b )
div = [ divisors of x <= mx ]
ans = div.len * mn
Is this close to the correct solution?
hmm...far away.
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.
That's because of '/' => for example you have 12 / 9 = 1, but 12 / 9 = 1.(3)
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$$$?
Yes, that's easy : you should find all divisors of common divisors of x and i
but there are some ugly cases such as $$$9\ /\ 8 * 7 = 9 * 7\ /\ 8$$$.
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 ?
Perhaps there is a $$$O(\ln x)$$$ or $$$O(\sqrt x)$$$ solution
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.
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)
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$$$.
Oh yes.
At first I forget a possibility of $$$c = 0$$$ (because of my poor logical mind)
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
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$$$.
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.
(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).
not x-x/i, x-(x/i)*i