Editorial for Proizvod
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Jedno od rešenja je da se samo pomnože brojevi tog intervala po modulu .
Međutim, interval može da bude dužine i do
, tako da ovo rešenje neće doneti maksimalan broj poena.
Primetimo da ako posmatramo uzastopnih brojeva, jedan od njih će sigurno biti deljiv sa
. To znači da ako je dati interval dužine veće ili jednake od
, on će sadržati barem jedan broj deljiv sa
. Dakle, proizvod brojeva tog intervala će biti deljiv sa
, odnsono proizvod će biti jednak
po modulu
.
Zadatak sada možemo podeliti u dva slučaja.
Kada je dužina intervala manja od (
). U tom slučaju dovoljno je proći kroz sve brojeve i pomnožiti ih. (
, pa ih neće biti više od
)
Kada je dužina intervala veća ili jednaka (
). U ovom slučaju traženi proizvod će biti
.
Comments