I have a math problem at school, but i haven't idea how to solve this problem
Given three natural numbers $$$n, a, b$$$. We define a pair $$$(x, y)$$$ as a beautiful pair if it satisfies all the following conditions:
- $$$1 \leq x \leq a$$$
- $$$1 \leq y \leq b$$$
- $$$(x \times y)$$$ is divisible by $$$(x + y)$$$ and the division result does not exceed $$$n$$$.
- $$$x$$$ and $$$y$$$ are natural numbers.
Requirement: Count the number of pairs $$$(x, y)$$$ that satisfy the conditions above and are considered beautiful pairs.
Input
- Contains three natural numbers $$$n, a, b$$$ $$$(1 \leq n, a, b \leq 10^{10})$$$.
- The data ensures that the result of the problem will not exceed $$$10^{18}$$$.
Output
- Print the result after performing the required task.
time limit per test: 2 seconds
can you help me how to solve this problem
(I use a translator to write this post, sorry for my bad English)
Auto comment: topic has been updated by dangthanhmay (previous revision, new revision, compare).
https://kilonova.ro/problems/314?list_id=92 (sorry for bad link, I’m on my phone).
thank you very much :)))
All that I can get, is that if xy / (x+y) = k, where k <= n, then xy = kx+ky. Move those k terms to the other side to get xy — ky — kx = 0. We can see that one part can be factorized rather nicely, as y(x-k) — kx = 0. So, I believe we should add k^2 to both sides to get (x-k)(y-k) on one side and k^2 on the other as (x-k)(y-k) = k^2 , which isn't too bad. But, we know x <= a and y <= b too. Hmm, if that were out, this would have been rather easy, but it isn't out. Now, we know that x-k and y-k are divisors of k^2. If x-k = divisor1, then we can easily see that divisor1 <= a -k, and similarly divisor2 <= b — k. divisor2 = y-k in case you didn't see.
Edit: SO, I left teh hard part out, and it svery hard, so, I think I dont know what to do