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

Does the inclusion–exclusion principle work?

Edited by author 08.09.2023 23:23

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