631 8
902 694
854 198
479 378
808 647
53 134
77 91
493 13
597 802
ans: 22

86 15
27 93
95 30
85 88
26 17
78 66
49 60
52 21
96 85
55 45
2 69
1 47
18 20
96 80
66 8
70 51
ans: 22

75 3
49 97
16 10
10 36
ans: 8

be more careful about formulas

i think my algo is right but i have problem with overflow in C++.
who can give me good test?

PS: on Pypy i have TL50 using the same algo( And it's very strange because on test
1000000000 18
1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 1
11 1
12 1
13 1
14 1
15 1
16 1
17 1
18 1

my algo works <300ms




PS: AC in C++ after many hacking with overflow. I hate this problem because spent a lot of time to fix problem with arighmetic (not algo)

Edited by author 12.12.2023 00:41

To solve the problem, you can use the inclusion-exclusion principle. The intersection of two arithmetic progressions can be found by solving the Diophantine equation. If the difference in the new progression is too large, you can replace it with n+1. It should be noted that the first element of the new progression must be no less than the first elements of the intersecting progressions. You should also consider possible type overflows. My implementation uses int128, but I think it is possible to solve it using int64.

Edited by author 15.07.2024 15:28

15 2
1 3
5 2

15 2
4 1
5 1

65 2
42 12
54 69


I think you have problems in formulas, I advise you to carefully read the articles with the theory

Edited by author 21.08.2023 22:05

Edited by author 21.08.2023 22:05

Use BINARY SEARCH, AFTER THIS TEST I GOT AC I'M SO GLAD, I'M JUST IN SHOCK. I hope all my tests will help you, I find this task very useful for number theory

if you have two progressions, one of which is with a very large step, then you can walk from the beginning of one progression to the beginning of the other

if you have two progressions, one of which is with a very large step, then you can walk from the beginning of one progression to the beginning of the other

dont use int128