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.

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.
Pentru o submultime de factori primi distincti ai lui K: P1, P2, .. , Pi vom calcula numarul de lanturi care au costul divizibil cu P1 * P2 * .. * Pi. Pentru a calcula acest numar vom face aceeasi dinamica ca inainte, doar ca vom folosi doar muchiile care au valoarea divizibila cu P1 * P2 * .. * Pi, acest lucru ne asigura faptul ca orice lant va avea costul divizibil cu P1 * P2 * .. *Pi.