I have two non lattice point like A=(3.34,6.23) ,B=(123.12,566.45)

How many lattice point on AB segment ?

# | User | Rating |
---|---|---|

1 | tourist | 3707 |

2 | Benq | 3672 |

3 | Radewoosh | 3655 |

4 | ksun48 | 3547 |

5 | jiangly | 3492 |

6 | Miracle03 | 3480 |

7 | ecnerwala | 3400 |

8 | maroonrk | 3385 |

9 | peehs_moorhsum | 3384 |

10 | sunset | 3338 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 216 |

2 | YouKn0wWho | 190 |

2 | Um_nik | 190 |

4 | sus | 183 |

5 | awoo | 182 |

6 | Errichto | 179 |

7 | tourist | 177 |

8 | -is-this-fft- | 173 |

9 | Radewoosh | 170 |

10 | maroonrk | 169 |

I have two non lattice point like A=(3.34,6.23) ,B=(123.12,566.45)

How many lattice point on AB segment ?

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/27/2021 14:25:52 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

$$$AB$$$ ： $$$y=\frac{2801100*x-5624527}{598900}$$$

Since $$$\gcd(2801100,598900)$$$ is not equal to $$$1$$$ , it does not yield a point such that $$$x$$$ and $$$y$$$ are both integers.

can you explain please?

If $$$x$$$ is an integer, $$$2801100x$$$ is divisible by $$$100$$$ no matter what, minus $$$5624527$$$, which is definitely not divisible by $$$100$$$ , but $$$598900$$$ is a multiple of one hundred, so you can't get an integer.

Auto comment: topic has been updated by aa_aa_aa (previous revision, new revision, compare).