A tökéletes mátrix élszomszédos celláiban relatív prím pozitív egész számok állnak, vagyis olyan egészek, amelyeknek nincs egynél nagyobb közös osztója, továbbá minden elem egynél nagyobb. 

Például:

12	25	3	8
5	49	121	5
3	4	21	6

Írjunk programot, ami egy adott A mátrixról eldönti, hogy van olyan B tökéletes mátrix, 

• aminek mérete azonos A méretével;
• és B _{i, j} osztója A _{i, j}-nek.

A bemenet első sora az A mátrix sorainak és oszlopainak számát adja meg (1 <= S, O <= 40),

Ezután S sorban O szám következik, A elemei. Ezek pozitív egész számok, továbbá 2 <= A _{i, j} <= 1000.

A kimenet első sora az 1 vagy 0 számot tartalmazza aszerint, hogy létezik vagy nem létezik megfelelő B mátrix.

Ha ez 1, akkor a következő sorokban egy megfelelő B mátrix elemei legyenek, a bemenetnek megfelelő sorrendben.

Bemenet	Kimenet
2 3 2 4 8 4 8 16	0
4 3 2 9 8 3 60 12 25 34 49 6 10 15	1 2 3 2 3 2 3 5 17 7 2 5 3

A feladat forrása: Bubble Cup - Student programming contest Serbia, 2010

Algoritmusok: visszalépéses keresés, backtrack

megoldás