Parells amb suma múltiple d'un nombre P15966

Statement

thehtml

Sigui m un natural. Donats n naturals, trobeu tots els parells de nombres (x, y) tals que x + y sigui múltiple d’m.

Entrada

L’entrada consisteix en diversos casos, cadascun amb un natural p (que s’explica més avall), una m entre 2 i 300, una n entre 2 i 5 · 10⁴, i els n naturals, tots diferents.

Sortida

Per a cada cas, considereu tots els parells amb suma múltiple d’m. Els nombres han d’estar ordenats dins de cada parell, i els parells han d’estar ordenats entre si (primer pel primer nombre i, en cas d’empat, pel segon).

Com que escriure tots els parells podria ocupar massa espai, escriviu només els parells saltant de p en p, començant pel primer. Per exemple, amb p=1 cal escriure tots els parells, amb p=2 un de cada dos, etc.

Escriviu 10 guions al final de cada cas.

Observacions

Els jocs de proves grossos s’han creat a l’atzar.
La vostre solució ha de ser eficient. Amb una solució que bàsicament comprovi tots els parells de nombres el jutge us donarà 50 punts, i podreu obtenir una nota màxima de 5 en aquest problema.
No podeu fer servir el tipus pair de C++.

Pista

Considereu el residu de cada nombre donat mòdul m.

Public test cases

Input

1 10 11  7 15 5 33 3 25 20 18 10 28 23
3 10 11  7 15 5 33 3 25 20 18 10 28 23
1 42 3  200 0 100
1 19 4  9 10 19 28

Output

3 7
5 15
5 25
7 23
7 33
10 20
15 25
----------
3 7
7 23
15 25
----------
----------
9 10
10 28
----------

Information

Author: Salvador Roura
Language: Catalan
Official solutions: C++
User solutions: C++ Python