Problema ne da un graf orientat aciclic unde nodurile sunt cluburile si muchiile sunt strazile dintre cluburui si ne cere sa calculam numarul de lanturi de cost 1. Costul unui lant este dat de cel mai mare divizor comun dintre valorile muchiilor de pe lant si o valoare K. Vom calcula numarul de lanturi de cost mai mare strict ca 1, deoarece vom vedea ca e mai usor sa calculam aceasta valoare, iar numarul de lanturi de cost 1 va fi numarul de lanturi posibile minus numarul de lanturi de cost mai mare strict ca 1.
Vom face sortarea topologica a grafului si numarul de lanturi posibile il vom calcula cu ajutorul programarii dinamice:

Dp[nod] = numarul de lanturi care incep din nod cu minim 2 noduri
Iar recurenta va fi: Dp[nod] = Suma din (Dp[vec] + 1), unde vec este un vecin al lui nod

Numarul de lanturi posibile este egal cu Suma din Dp[nod], pentru orice nod.
Acum trebuie sa calculam numarul de lanturi cu costul mai mare strict ca 1. Putem observa ca orice lant are costul egal cu cel mai mare divizor dintre (K, alte numere) => costul unui lant este divizibil cu cel putin un factor prim al lui K.
Pentru fiecare factor prim P al lui K putem calcula numarul de lanturi care au costul divizibil cu P, astfel vom afla numarul de lanturi cu costul mai mare strict ca 1. Pentru a nu lua in considerare un lant de mai multe ori ne vom folosi de principiul includerii si excluderii pe factorii primi distincti ai lui K.