Omówienie zadania Modified GCD (Codefoces C.) – NWD / Wyszukiwanie binarne

Omówienie zadania Modified GCD (Codefoces C.) – NWD / Wyszukiwanie binarne

Szczegółowe omówienie zadania Modified GCD:

Link do powyższego omówienia zadania Modified GCD:
https://youtu.be/2RV8_naxzHE?t=5720
Link do treści zadania Modified GCD:

————
Zadanie Modified GCD to zadanie które ćwiczy NWD oraz wyszukiwanie binarny (binary search).
Wymaga też prostego pomysłu.

————
Zadanie pochodzi z platformy Codeforces – najbardziej popularnej światowej platformy programistyczni -algorytmicznej.
Daje nam piękny wpis do CV:
https://youtu.be/QgLyXYmFQeU?t=3507

——–
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 Modified GCD, który jest omówiony w powyższym filmie i który otrzymuje 100%


#include<bits/stdc++.h>
using namespace std;

vector<int>Dzielniki;

int NWD(int a, int b){
	int c;
	while(b!=0){
		c=a%b;
		a=b;
		b=c;
	}
	return a;
}

int NWDRek(int a, int b){
	if( a==0 || b==0 ) return max(a, b);
	if(a>b)  return NWD(a%b, b);
	if(a<b)  return NWD(a, b%a);
}

int PierwszyMniejszyRowny(int h){
	int p, k, s;
	p=0;
	k=(int)Dzielniki.size()-1;
	while(p<k){
		s=(p+k+1)/2;
		if(Dzielniki[s]>h) k=s-1;
		else p=s;
	}
	return Dzielniki[p];
}

int main (){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int a, b, nwd, i, q, low, high, wynik, pierw;
	cin>>a>>b;
	nwd=NWD(a, b); 
	//nwd=__gcd(a, b);
	//nwd=NWDRek(a, b);
	pierw=(int)sqrt(nwd);
	for(i=1; i<=pierw; i++){
		if( (nwd%i) != 0 ) continue;
		Dzielniki.push_back(i);
		Dzielniki.push_back(nwd/i);
		if( i*i==nwd ) Dzielniki.pop_back();
	}
	sort( Dzielniki.begin(), Dzielniki.end() );
	cin>>q;
	for(i=1; i<=q; i++){
		cin>>low>>high;
		wynik=PierwszyMniejszyRowny(high);
		if(wynik<=high && wynik>=low) cout << wynik << "\n";
		else cout << "-1\n";
	}
	return 0;
}
Link do pliku ze wzorcowym kodem C++ zadania C. Modified GCD 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz