Given two arithmetic sequences (a1,d1 i.e. first term and common difference of first sequence and similarly a2,d2),what is the best algorithm to tell whether they have any common term,and if yes then tell the lowest one.

Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems.
×

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

1 | MiFaFaOvO | 3681 |

2 | tourist | 3669 |

3 | Um_nik | 3535 |

4 | 300iq | 3317 |

5 | ecnerwala | 3294 |

6 | maroonrk | 3268 |

7 | TLE | 3223 |

8 | scott_wu | 3209 |

9 | WZYYN | 3180 |

10 | boboniu | 3174 |

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

1 | Errichto | 197 |

2 | antontrygubO_o | 187 |

3 | Ashishgup | 182 |

3 | pikmike | 182 |

5 | vovuh | 179 |

6 | Radewoosh | 168 |

7 | Um_nik | 164 |

8 | tourist | 163 |

8 | Monogon | 163 |

10 | McDic | 162 |

Given two arithmetic sequences (a1,d1 i.e. first term and common difference of first sequence and similarly a2,d2),what is the best algorithm to tell whether they have any common term,and if yes then tell the lowest one.

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/09/2020 08:54:10 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Let's say a[x]=b[y]. Then a1+d1*x=a2+d2*y or d1*x-d2*y=a2-a1. So, you just need to solve Diophantine equation.

I knew this method.I was wondering if there is any other way.

I think this can be done with the Chinese Remainder Theorem. A term in both sequences is congruent to a1 (mod d1) and to a2 (mod d2), so you can find a number x such that any common term must be equal to x (mod lcm(d1, d2)) using Chinese Remainder Theorem (assuming there is at least one common term). Then, you can take the smallest value with that mod value that is greater than or equal to max(a1, a2).