Programowanie i algorytmy

Liczby doskonałe

Liczba doskonała to taka, której suma dzielników właściwych jest jej równa. Do zbioru liczb doskonałych należy liczba 6, ponieważ:

D6 = {1, 2, 3, 6}

6 = 1 + 2 + 3

lub 28:

D28 = {1, 2, 4, 7, 14, 28}

28 = 1 + 2 + 4 + 7 + 14

Ciekawostką jest, że nie udało się nikomu jeszcze znaleźć nieparzystej liczby doskonałej, nawet nie istnieje na to dowód, czy jest taka. Nie wiadomo także, czy takich liczb jest nieskończenie wiele. Jednym ze sposobów szukania ich, jest określanie sum dzielników liczb w danym przedziale i badanie ich właściwości, i takie jest twoje zadanie. Dla danego przedziału [a, b], znajdź najmniejszą liczbę naturalną należącą do tego przedziału, której suma dzielników jest równa n (pod uwagę bierzemy wszystkie dzielniki naturalne danej liczby).

Uwaga! Algorytm wzorocowy oparty jest na wczytywaniu scanf'em i wypisuwaniu printf'em w języku C++.

 

 

Wejście

W pierwszym wierszu jedna liczba naturalna t określająca liczbę zestawów danych (t < 106).

Każdy zestaw danych składa się z trzech liczb: a, b i n, gdzie 0 < ab ≤ 106 i 0 < n ≤ 106 .

Wyjście

Dla każdego zestawu szukana liczba lub napis "brak" jeśli taka liczba nie istnieje.

Przykład

Wejście:
3
2 10 3
2 10 4
2 10 5

Wyjście:
2
3
brak

Szkic rozwiązania

W tym zadaniu należy wykonać podwójny preprocessing danych. Najpierw w tablicy tab[1000001] zapamiętujemy wszystkie sumy dzielników:

komórka tab[i] będzie pamiętać sumę dzielników liczby i:

 
tab[1000001] = {};
 
for(i=1;i<1000001;i++)
  for(j=i;j<1000001;j+=i)
    tab[j] += i;
 

 W drugim kroku tworzymy strukturę 1000001 - elementową, w której pod indeksem i będziemy pamiętać wszystkie liczby, których suma dzielników jest równa i. Przeszukujemy liniowo tablicę tab i zapisujemy kolejne liczby do struktury.

struct sumy_dzielnikow{
  vector suma;
}S[1000001];
 
for(i=1;i<=1000001;i++)
  if(tab[i]<1000001)
    S[tab[i]].push_back(i);
 
 
 

 

Zauważmy, że dla niektórych sum dzielników, może być wiele takich liczb, które będą zapamiętane rosnąco. Dzięki tej informacji możemy użyć przeszukiwania binarnego dla zapytań.