Problem description

Back

Show PDF

.desc_header { margin-bottom: 2em; text-align: center; } .desc_title { font-size: 200%; text-decoration: underline; padding: 0em 0.2em; display: inline-block; } .desc_code { padding: 0em 0.2em; font-weight: bold; display: inline-block; } .desc_meta { margin: 0.5em; } .desc_memlimit { padding: 0em 1.25em; display: inline-block; } .desc_timelimit { padding: 0em 1.25em; display: inline-block; } .desc .example-test { width: 100%; margin-top: 10px; } .desc .example-test td { vertical-align: top; } .desc .example-test pre { margin-top: 5px; } NWW (nww-setadd) Limit pamięci: 32 MB Limit czasu: 1.50 s Jasio kupił sobie nowiutki zbiór liczb naturalnych. Szybko obliczył najmniejszą wspólną wielokrotność liczb w tym zbiorze. Zaczął się teraz zastanawiać nad tym ile liczb mógłby dodać do swojego zbioru, aby NWW nie uległa zmianie. Pomóż mu! Napisz program, który: wczyta zbiór liczb Jasia, wyznaczy maksymalną liczbę liczb, które można dodać do zbioru, aby NWW nie uległa zmianie i wypisze wynik na standardowe wyjście. Wejście W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, określająca moc zbioru Jasia. W drugim (ostatnim) wierszu wejścia znajduje się ciąg parami różnych N liczb naturalnych Ai poodzielanych pojedynczymi odstępami – liczby w zbiorze Jasia. Wyjście W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba naturalna – reszta z dzielenia przez 109 + 7 maksymalnej liczby liczb, które można dodać do zbioru, aby NWW liczb ze zbioru nie uległa zmianie. Ograniczenia 1 ≤ N ≤ 50 000, 1 ≤ Ai ≤ 109. Przykład Wejście Wyjście Wyjaśnienie 3 1 4 6 3 NWW zbioru Jasia ({1, 4, 6}) jest równe 12. Po dodaniu elementów 2, 3 oraz 12 otrzymujemy zbiór {1, 2, 3, 4, 6, 12}, którego NWW jest również równe 12.

Wejście	Wyjście	Wyjaśnienie
`3 1 4 6`	`3`	NWW zbioru Jasia ({1, 4, 6}) jest równe 12. Po dodaniu elementów 2, 3 oraz 12 otrzymujemy zbiór {1, 2, 3, 4, 6, 12}, którego NWW jest również równe 12.