| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3648 |
| 2 | Benq | 3580 |
| 3 | orzdevinwang | 3570 |
| 4 | cnnfls_csy | 3569 |
| 5 | Geothermal | 3568 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3530 |
| 8 | Radewoosh | 3520 |
| 9 | Um_nik | 3481 |
| 10 | jiangly | 3467 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | adamant | 164 |
| 2 | awoo | 164 |
| 4 | TheScrasse | 160 |
| 5 | nor | 159 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 150 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
Hi. I've been struggling to solve this problem from UVA.
It asks for the number of lattice points ( points with integer co-ordinates ) on a given line segment. But the endpoints on the segment can be fractions. I'll appreciate it a lot if someone tells me how this problem can be solved.
Auto comment: topic has been updated by Aritra741 (previous revision, new revision, compare).
I looked at the problem; there's a pretty important point made in the problem statement. The points of the segment have exactly one digit after the decimal. One really common trick here (pops up when you deal with dollars as well, which have two points after the decimal point) is to multiply everything by a number so that your points are all integers. Here you can multiply by 10, and then your problem is reduced to finding all the integer lattice points (x, y) such that x and y are multiples of 10. Do you think figuring that out would be easier?
Great observation, Thanks. It does sound easier, but I can only think of ways to find the number of total lattice points of the new line after multiplying by 10, not exactly the number of points which are multiples of 10. Could you please give more hints about how it can be done?
Hint: it's not a geometry problem, it's a number theory problem.
Thanks. Kindly let me know if this approach is correct: Initially I have the equation of the line that goes through those two points, which is a linear diophantine equation. Multiplying that equation by 10 will produce a new equation. Now the task is to find the number of solutions of this new equation inside the given constraints*10.