Omówienie zadania GCD Table (Codeforces)

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