Fişierul intrare/ieşire:treegcd.in, treegcd.outSursăONI 2019, clasele 11-12
AutorDenis BanuAdăugată deAlexPop28Pop Alex-Nicolae AlexPop28
Timp execuţie pe test0.3 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

TreeGCD

Când era în vizită la bunici, Cătălin a descoperit în garaj o consolă Nintendo din anul 1970. Din fericire, această consolă avea şi un joc. Acest joc se chema “TreeGCD”. Cătălin primeşte un arbore cu N noduri şi un număr M. El trebuie să spună în câte moduri poate să atribuie fiecărui nod un număr de la 1 la M, astfel încât oricare două noduri adiacente să nu aibă atribuite numere prime între ele (adică cel mai mare divizor comun este strict mai mare ca 1).

Cerinţă

Determinaţi care este numărul de moduri în care putem atribui fiecărui nod câte un număr de la 1 la M, astfel încât oricare două noduri care sunt legate printr-o muchie să nu aibă atribuite numere prime între ele. Numărul trebuie afişat modulo 1.000.000.007.

Date de intrare

În fişierul treegcd.in se află pe prima linie două numere naturale nenule N şi M, separate printr-un spaţiu. Pe fiecare din următoarele N-1 linii se află câte două numere naturale nenule x şi y, separate printr-un spaţiu, cu semnificaţia că nodurile x şi y sunt adiacente.

Date de ieşire

În fişierul treegcd.out trebuie să se găsească un singur număr. Acest număr reprezintă în câte moduri se poate atribui fiecărui nod o valoare de la 1 la M, astfel încât pentru oricare două noduri adiacente, valorile asociate să nu fie prime între ele. Deoarece rezultatul poate fi foarte mare, se va afişa restul modulo 109 + 7 pentru numărul cerut.

Restricţii

  • 2 ≤ N ≤ 100
  • 2 ≤ M ≤ 10.000
  • pentru teste în valoare de 4 puncte avem N = 2 şi M ≤ 1.000.
  • pentru alte teste în valoare de 13 puncte avem N ≤ 6 şi M ≤ 10.
  • pentru teste în valoare de 40 de puncte avem N ≤ 100 şi M ≤ 100.
  • pentru alte teste în valoare de 43 de puncte avem N ≤ 100 şi M ≤ 10.000.

Exemplu

treegcd.intreegcd.outExplicaţii
2 6
1 2
13
Perechile de valori asociate nodurilor 1, 2 sunt:
(2,2), (2,4), (2,6), (3,3), (3,6), (4,2), (4,4),
(4,6), (5,5), (6,2), (6,3), (6,4), (6,6).
5 6
5 3
3 1
5 4
3 2
397
Rezultatul este 397.
10 67
1 2
1 3
2 4
2 5
2 6
2 7
5 8
5 9
7 10
534323877
Rezultatul este 6315455578532062, iar
6315455578532062 % 1000000007 = 534323877
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?