Fişierul intrare/ieşire:tenerife.in, tenerife.outSursăFMI No Stress 9
AutorStelian ChichirimAdăugată defminostress9FMI No Stress 9 fminostress9
Timp execuţie pe test1.5 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Tenerife

Un grup de studenti pleaca pe insula Tenerife in vacanta. Acestia vor sa se distreze, dar vor sa cheltuiasca cat mai putini bani. Insula Tenerife este formata din N cluburi si M strazi unidirectionale.
Fiecare strada este data prin X, Y si C, care semnifica ca poti merge din clubul X in clubul Y cu un cost C, dar nu si invers. Deoarece insula e construita astfel incat lumea sa nu se plictiseasca, din orice club ai pleca nu vei putea ajunge inapoi in clubul de pornire mergand pe strazi. O excursie este formata din mai multe cluburi X1, X2, ... , Xp, p >= 2, astfel incat exista strada de la X1 la X2, de la X2 la X3, ... , de la Xp-1 la Xp, iar costul unei astfel de excursii este cel mai mare divizor comun dintre (K, costul strazii de la X1 la X2, costul strazii de la X2 la X3, ... , costul strazii de la Xp-1 la Xp). Deoarece studentii nu au multi bani, acestia vor sa faca excursii cu costul egal cu 1.
Ajuta-i pe studenti si calculeaza numarul de excursii diferite care au costul egal cu 1. Deoarece acest numar poate fi foarte mare, trebuie sa il afisati modulo 1000000007. 

Date de intrare

Fişierul de intrare tenerife.in contine pe prima linie N, M si K.
Urmeaza M linii, fiecare avand 3 numere, X, Y si C, care semnifica ca exista muchie orientata de la clubul X la clubul Y cu costul C.

Date de ieşire

În fişierul de ieşire tenerife.out se va afisa numarul de excursii diferite care au costul egal cu 1 modulo 1000000007.

Restricţii

  • 1 <= N <= 50.000
  • 1 <= M <= 100.000
  • 1 <= C, K <= 109
  • O excursie trebuie sa aiba minim 2 cluburi
  • Pentru 10% din punctaj N <= 1000 si graful va avea forma de lant orientat intr-o singura parte.
  • Pentru alte 10% din punctaj K = 1.
  • Pentru alte 10% din punctaj K este numar prim.
  • Pentru alte 20% din punctaj K <= 5000.
  • Pentru alte 50% din punctaj restrictiile initiale.

Exemplu

tenerife.intenerife.out
7 7 66
1 3 2
2 3 3
3 4 6
3 5 5
5 6 7
4 6 35
7 5 15
12
10 12 840
1 2 2
1 3 10
2 3 6
3 4 15
4 5 10
5 6 25
6 7 35
7 8 50
8 9 20
9 10 49
1 9 42
4 6 200
33

Explicaţie

Pentru primul exemplu:

Excursiile care au costul egal cu 1 sunt:
1) 3 -> 5
2) 5 -> 6
3) 4 -> 6
4) 1 -> 3 -> 5
5) 2 -> 3 -> 5
6) 3 -> 5 -> 6
7) 3 -> 4 -> 6
8) 7 -> 5 -> 6
9) 1 -> 3 -> 4 -> 6
10) 1 -> 3 -> 5 -> 6
11) 2 -> 3 -> 5 -> 6
12) 2 -> 3 -> 4 -> 6

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?