Rezumat problemă

gcd_tree

#4670

RAU-Gigel și Vlad sunt prieteni buni și le place tot timpul să se provoace unul pe altul. De data aceasta, RAU-Gigel a inventat o problemă interesantă de matematică.

Acesta are un arbore secret cu N noduri (numerotate de la 1 la N), în care fiecare nod are asociată o valoare (pe lângă numărul său de ordine din arbore), care este un număr natural și ii spune lui Vlad informații despre unele drumuri din acest arbore. O informație are forma x, y, val și reprezintă faptul că lanțul din arbore de la nodul x la nodul y are cel mai mare divizor comun al valorilor asociate nodurilor acestuia egal cu val, unde val este un număr natural nenul.

Vlad știe că RAU-Gigel minte câteodată și s-ar putea ca unele dintre restricțiile date să fie eronate, astfel că vrea să afle întâi folosind informațiile ce le are la îndemână dacă ar putea exista un arbore care să respecte toate restricțiile date de prietenul său.

Pentru că știe ce programator iscusit ești, Vlad ți-ar fi foarte recunoscător daca l-ai putea ajuta cu această problemă prin a scrie un program care să o rezolve cât mai eficient.

RAU-Coder 2024

Fișiere Lorintz Alexandru (Alex_tz307) Alexandru Lorintz concurs

Clasa 11 Structuri de date arborescente Structuri de date Arbori de intervale Algoritmul lui Euclid Range Minimum Query Lowest Common Ancestor Heavy-Light Decomposition

Rezolvă

Detalii

Problema	gcd_tree	Operații I/O	gcd_tree.in/gcd_tree.out
Limita timp	2 secunde	Limita memorie	Total: 256 MB / Stivă 64 MB
Id soluție	#62662674	Utilizator	Luncan Raul (raulluncan)
Fișier	gcd_tree.cpp	Dimensiune	6.25 KB
Data încărcării	28 Ianuarie 2026, 23:02	Scor/rezultat	Eroare de compilare

Evaluare

Mesaj compilare

gcd_tree.cpp: In function 'long long int lcm_ll(long long int, long long int)':
gcd_tree.cpp:5:16: error: 'gcd' is not a member of 'std'
     return a / std::gcd(a, b) * b;

                ^
gcd_tree.cpp: In member function 'void SegGCD::build(const std::vector<long long int>&)':
gcd_tree.cpp:60:50: error: 'gcd' is not a member of 'std'
         for (int i = n - 1; i >= 1; i--) st[i] = std::gcd(st[i << 1], st[i << 1 | 1]);

                                                  ^
gcd_tree.cpp: In member function 'long long int SegGCD::query(int, int) const':
gcd_tree.cpp:67:31: error: 'gcd' is not a member of 'std'
             if (l & 1) resL = std::gcd(resL, st[l++]);

                               ^
gcd_tree.cpp:68:34: error: 'gcd' is not a member of 'std'
             if (!(r & 1)) resR = std::gcd(st[r--], resR);

                                  ^
gcd_tree.cpp:71:16: error: 'gcd' is not a member of 'std'
         return std::gcd(resL, resR);

                ^
gcd_tree.cpp: In member function 'void HLD::build(int)':
gcd_tree.cpp:140:18: error: expected unqualified-id before '[' token
             auto [u0, h] = stack2.back();

                  ^
gcd_tree.cpp:142:21: error: 'u0' was not declared in this scope
             int u = u0;

                     ^
gcd_tree.cpp:143:27: error: 'h' was not declared in this scope
             int curHead = h;

                           ^
gcd_tree.cpp: In function 'int main()':
gcd_tree.cpp:205:19: error: expected unqualified-id before '[' token
         for (auto [x, y, val] : cons) {

                   ^
gcd_tree.cpp:205:19: error: expected ';' before '[' token
gcd_tree.cpp:205:20: error: 'x' was not declared in this scope
         for (auto [x, y, val] : cons) {

                    ^
gcd_tree.cpp:205:23: error: 'y' was not declared in this scope
         for (auto [x, y, val] : cons) {

                       ^
gcd_tree.cpp:205:26: error: 'val' was not declared in this scope
         for (auto [x, y, val] : cons) {

                          ^
gcd_tree.cpp: In lambda function:
gcd_tree.cpp:205:31: error: expected '{' before ':' token
         for (auto [x, y, val] : cons) {

                               ^
gcd_tree.cpp: In function 'int main()':
gcd_tree.cpp:205:31: error: expected ';' before ':' token
gcd_tree.cpp:205:31: error: expected primary-expression before ':' token
gcd_tree.cpp:205:31: error: expected ')' before ':' token
gcd_tree.cpp:205:31: error: expected primary-expression before ':' token
gcd_tree.cpp:205:31: error: expected ';' before ':' token
gcd_tree.cpp:238:1: error: expected '}' at end of input
 }

 ^
gcd_tree.cpp:238:1: error: expected '}' at end of input
gcd_tree.cpp:176:39: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("gcd_tree.in", "r", stdin);

                                       ^
gcd_tree.cpp:177:41: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("gcd_tree.out", "w", stdout);

                                         ^

Cum funcționează evaluarea?