Omówienie zadania GCD Table (Codeforces)

Szczegółowe omówienie zadania GCD Table:

Link do powyższego omówienia zadania GCD Table:
https://youtu.be/OC_xrHSMYlA?t=4370
Link do treści zadania GCD Table:
https://codeforces.com/problemset/problem/582/A
——–
Zadanie GCD Table wymaga pomysłu i znajomości algorytmu liczenia Największego Wspólnego Dzielnika NWD (ang. GCD).
Jak liczyć NWD?
https://youtu.be/9pX9VAosgTY?t=4344
oraz
https://youtu.be/9pX9VAosgTY?t=4650
Kod NWD:
https://youtu.be/9pX9VAosgTY?t=5439——–
Zadanie GCD Table pochodzi z dywizji I – najtrudniejszej w Codeforces i  daje fantastyczny wpis do CV:
https://youtu.be/OC_xrHSMYlA?t=6050

——–
Jak się uczyć na podstawie tego zadania?
https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz:
https://youtu.be/pkLXuuOe_qA?t=3625

——-
Kod C++ programu GCD Table, który jest omówiony w powyższym filmie i który otrzymuje 100%


#include<bits/stdc++.h>
using namespace std;
const int N=510;
multiset<int>Tablica;
int Wynik[N];
multiset<int>::iterator it;
int NWD(int a, int b){
int c;
while(b!=0){
c=a%b;
a=b;
b=c;
}
return a;
}
int main (){
int n, a, aktu_max, aktu_indeks;
cin>>n;
for(int i=1; i<=n*n; i++){
cin>>a;
Tablica.insert(a);
}
aktu_indeks=1;
while( !Tablica.empty() ){
it=Tablica.end(); it--;
		aktu_max=*it;
Wynik[aktu_indeks]=aktu_max;
it=Tablica.find( aktu_max );
Tablica.erase( it );
for(int i=1; i<aktu_indeks; i++){
it=Tablica.find( NWD(aktu_max, Wynik[i]) );
Tablica.erase(it);
it=Tablica.find( NWD(aktu_max, Wynik[i]) );
Tablica.erase(it);
}
aktu_indeks++;
}
for(int i=1; i<=n; i++) cout << Wynik[i] << " ";
cout<<"\n";
return 0;
}
Link do pliku ze wzorcowym kodem C++ zadania GCD Table 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz