Diferente pentru problema/tenerife intre reviziile #20 si #37

Diferente intre titluri:

tenerife
Tenerife

Diferente intre continut:

== include(page="template/taskheader" task_id="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 in acelasi club mergand pe strazi. O excursie este formata din mai multe cluburi X{~1~}, X{~2~}, ... , X{~p~}, p >= 2, astfel incat exista strada de la X{~1~} la X{~2~}, de la X{~2~} la X{~3~}, ... , de la X{~p-1~} la X{~p~}, iar costul unei astfel de excursii este cel mai mare divizor comun dintre ({*K*}, costul strazii de la X{~1~} la X{~2~}, costul strazii de la X{~2~} la X{~3~}, ... , costul strazii de la X{~p-1~} la X{~p~}). Deoarece studentii nu au multi bani, acestia vor sa faca excursii cu costul egal cu 1.
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 X{~1~}, X{~2~}, ... , X{~p~}, p >= 2, astfel incat exista strada de la X{~1~} la X{~2~}, de la X{~2~} la X{~3~}, ... , de la X{~p-1~} la X{~p~}, iar costul unei astfel de excursii este cel mai mare divizor comun dintre ({*K*}, costul strazii de la X{~1~} la X{~2~}, costul strazii de la X{~2~} la X{~3~}, ... , costul strazii de la X{~p-1~} la X{~p~}). 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.
h2. Date de intrare
h2. 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.
În fişierul de ieşire $tenerife.out$ se va afisa numarul de excursii diferite care au costul egal cu $1$ modulo 1000000007.
h2. Restricţii
* 1 <= N <= 100.000
* 1 <= M <= 200.000
* 1 <= K, C <= 10^9^
* 1 <= N <= 50.000
* 1 <= M <= 100.000
* 1 <= C, K <= 10^9^
* {*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 20% din punctaj K este numar prim.
* Pentru alte 60% din punctaj restrictiile initiale.
* 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.
h2. Exemplu
 5 6 7
 4 6 35
 7 5 15
| 12
|
| 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
|
 
h3. Explicaţie
Pentru primul exemplu:
 
Excursiile care au costul egal cu 1 sunt:
1) 3 -> 5
2) 5 -> 6

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.