Szczegółowe omówienie zadania Najmniejsza Wspólna Wielokrotność:
Link do powyższego omówienia zadania Najmniejsza Wspólna Wielokrotność:
https://youtu.be/vGXde_OyNME?t=168
Omówienie kodu zadania Najmniejsza Wspólna Wielokrotność:
https://youtu.be/kH-_PQyAs9A?t=3449
——-
Link do treści zadania Najmniejsza Wspólna Wielokrotność:
——
Zadanie Najmniejsza Wspólna Wielokrotność jest prostym zadaniem które realizuje strategie “Policzy Najpierw Wszystko”.
Wydaje się to na początku zaskakujące, ale możemy znaleźć wszystkie liczby które są NWW innych kolejnych liczb.
Jednocześnie zadanie Najmniejsza Wspólna Wielokrotność wymaga znajomości szybkiego algorytmu Euklidesa dla obliczania Największego Wspólnego Dzielnika. NWD jest nam potrzebne do obliczania NWW.
Implementacja zadania jest prosta – klika linii.———–
Zrobienie tego zadania – bez względu na punktu – daje ogromną motywację do rozwoju bo widzimy, że Olimpiada Informatyczna jest w naszym zasięgu.
Wydaje się to na początku zaskakujące, ale możemy znaleźć wszystkie liczby które są NWW innych kolejnych liczb.
Jednocześnie zadanie Najmniejsza Wspólna Wielokrotność wymaga znajomości szybkiego algorytmu Euklidesa dla obliczania Największego Wspólnego Dzielnika. NWD jest nam potrzebne do obliczania NWW.
Implementacja zadania jest prosta – klika linii.———–
Zrobienie tego zadania – bez względu na punktu – daje ogromną motywację do rozwoju bo widzimy, że Olimpiada Informatyczna jest w naszym zasięgu.
—–
Zadanie Najmniejsza Wspólna Wielokrotność pochodzi z I etapu 27 Olimpiady Informatycznej Szkół Ponadpodstawowych.
Link do wszystkich zadań z Olimpiady Informatycznej:
https://szkopul.edu.pl/task_archive/oi/
Zadanie Najmniejsza Wspólna Wielokrotność pochodzi z I etapu 27 Olimpiady Informatycznej Szkół Ponadpodstawowych.
Link do wszystkich zadań z Olimpiady Informatycznej:
https://szkopul.edu.pl/task_archive/oi/
——–
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
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
——-
–
#include <bits/stdc++.h>
using namespace std;
const long long int MAX_LICZBA = 1e18;
const long long int MAX_POCZATEK = 1.26e6;
map < long long int, pair<int, int> > najlepszy_przedzial;
long long int NWD(long long int a, long long int b){
long long int c;
while ( b != 0) {
c = a % b;
a = b;
b = c;
}
return a;
}
int main(){
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
int poczatek, koniec;
long long int akt_nwd, iloczyn_nww;
long long int pytana_liczba;
long long int pierwiastek;
int liczba_pytan, i;
for (poczatek=1; poczatek<=MAX_POCZATEK; ++poczatek) {
koniec = poczatek+1;
akt_nwd = NWD(koniec, poczatek);
iloczyn_nww = ((long long)poczatek/akt_nwd) * (long long)koniec;
while (1) {
++koniec;
akt_nwd = NWD(iloczyn_nww, koniec);
if ( (iloczyn_nww/akt_nwd) > (MAX_LICZBA/koniec) )
break;
iloczyn_nww = (iloczyn_nww/akt_nwd) * (long long)koniec;
if ( najlepszy_przedzial.find(iloczyn_nww) == najlepszy_przedzial.end() ) { //pierwszy raz wpisujemy dla nww 3 licb
najlepszy_przedzial[iloczyn_nww] = make_pair(poczatek, koniec);
}
}
}
cin >> liczba_pytan;
for (i=1; i<=liczba_pytan; ++i) {
cin >> pytana_liczba;
if ( najlepszy_przedzial.find(pytana_liczba) != najlepszy_przedzial.end() ) {
cout << najlepszy_przedzial[pytana_liczba].first << " " << najlepszy_przedzial[pytana_liczba].second << "\n";
continue;
}
pierwiastek = sqrt(pytana_liczba);
if ( (pierwiastek*pierwiastek) >= pytana_liczba )
--pierwiastek;
if ( pierwiastek*(pierwiastek+1) == pytana_liczba ) {
cout << pierwiastek << " " << pierwiastek+1 << "\n";
continue;
}
cout << "NIE\n";
}
return 0;
}