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
Unable to parse markup [type=CF_MATHJAX]
?Yes, that's easy : you should find all divisors of common divisors of x and i
but there are some ugly cases such as
Unable to parse markup [type=CF_MATHJAX]
.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 ?Perhaps there is a
Unable to parse markup [type=CF_MATHJAX]
or $$$O(\sqrt x)$$$ solutionI 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
Unable to parse markup [type=CF_MATHJAX]
($$$a,b,c,d$$$ is all integers andUnable 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 toUnable 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)
I don't think you're considering the correct possibilities. For
Unable to parse markup [type=CF_MATHJAX]
, you needUnable to parse markup [type=CF_MATHJAX]
andUnable to parse markup [type=CF_MATHJAX]
. ForUnable to parse markup [type=CF_MATHJAX]
, Case 1 is, eitherUnable 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 meansUnable to parse markup [type=CF_MATHJAX]
, orUnable to parse markup [type=CF_MATHJAX]
, which means, when $$$j<i$$$ you need to count only whenUnable to parse markup [type=CF_MATHJAX]
. So totally, you need to count all $$$(i,j)$$$ where1). $$$i$$$ divides $$$x$$$ ( $$$j$$$ can be any ).
(OR)
2). $$$j<i$$$ and
Unable to parse markup [type=CF_MATHJAX]
.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
Unable to parse markup [type=CF_MATHJAX]
, we need to count number of $$$j$$$ such that $$$j<i$$$ ansUnable 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 asUnable 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 forUnable 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$$$.Do you notice that "$$$x$$$ must be a multiple of $$$i$$$"or "$$$j < i$$$ and
Unable to parse markup [type=CF_MATHJAX]
" can merge toUnable 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.
(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