Algoritmi – primeri (NZD, prosti brojevi, faktorizacija)

Dat je niz prirodnih brojeva dužine N manjih od M.
Naći maksimalnu dužinu podniza fibonačijevog niza tako da on može biti formiran od zadatih brojeva i ispisati indekse elemenata zadatog niza koji formiraju ovaj fibonacijev podniz.

Ulaz
U prvom redu standardnog ulaza nalaze se prirodni brojevi N i M koji predstavljaju broj elemenata i maksimalnu moguću vrednost elemenata zadatog niza.
U drugom redu nalazi se N prirodnih brojeva koji predstavljaju zadati niz.

Izlaz
Na standardni izlaz u prvom redu ispisati broj elemenata najdužeg fibonačijevog podniza koji se može formirati i ispisati indekse elemenata zadatog niza koji formiraju ovaj fibonacijev podniz. Ukoliko postoje dva ista broja sa razlicitim indeksom u nizu uzeti manji indeks. Indekse ispisati u redu takvom da elementi niza, koje oni indeksiraju, formiraju fibonacijev podniz.

Ograničenja
M <= 10 000;
N <= 10 000 000;

Primer
Ulaz
12
20
Izlaz
2 4 6 8 10 11 13 4 3 2 1 1
4
10 11 0

Dato je n brojeva. Potrebno je faktorisati svaki broj, tj. napisati ga kao proizvod prostih činilaca. Svaki broj faktorisati u formatu p1^a1 * p2^a2 * ... * pk^ak , gde su p1 ≤ p2 ≤ ... ≤ pk svi prosti činioci datog broja (u rastućem redosledu), a a1, a2, ..., ak - njihovi odgovarajući izložioci. Izmedju brojeva i simbola '*' i '^' ne sme biti razmaka. Takođe, ukoliko je izložilac nekog broja jednak 1, treba ga svejedno ispisati.Ulaz
U prvom redu standradnog ulaza nalazi se prirodan broj n . U sledećih n redova se nalazi po jedan ceo broj bi koga treba faktorisati.

Izlaz
Na standardni izlaz za svaki broj ispisati, u posebnom redu, njegovu faktorizaciju u gore opisanom formatu, u redosledu datim na ulazu.

Ograničenja
1 ≤ n ≤ 200.000,
2 ≤ bi ≤ 200.000.

Dat je prirodan broj N. Odrediti koliko ima parova prostih brojeva p i q, tako da je p ≤ q i da je p+q takođe prost broj koji je manji ili jednak od N.Ulaz
U prvom i jedinom redu standardnog ulaza nalazi se prirodan broj N.

Izlaz
U prvom i jedinom redu standardnog izlaza ispisati traženi broj parova prostih brojeva.

Ograničenja
1 ≤ N ≤ 1.000.000
Primer
Ulaz
6

Izlaz
1

Objašnjenje primera
Postoji samo jedan par koji zadovoljava uslove a to je (2, 3). Zaista, 2 i 3 su prosti brojevi i 2+3 je prost broj koji je manji ili jednak od 6.

Za brojeve p i qkažemo da su k-prosto udaljeni ukoliko su oni prosti i između njih postoji tačno kprostih brojeva. Vama su dati brojevi Ni k. Poznato je da je broj Nili prost ili se može zapisati u obliku proizvoda p1·p2·p3·...·pm, gde za svako 1 ≤ i ≤ m - 1važi pi < p_{i+1} i pi i p_{i+1} su k-prosto udaljeni brojevi. Nažalost, mi ne znamo broj m niti brojeve pi - vaš zadatak je da faktorisete broj N, tj. da ga napišete u obliku proizvoda prostih brojeva.Ulaz
U jednom test primeru je potrebno faktorisati više brojeva N.
U prvom redu standardnog ulaza se nalazi prirodan broj T - broj parova (N, k) iz opisa problema. U svakom od narednih T redova se nalaze, redom, brojevi N i k, razdvojeni razmakom.

Izlaz
Na standarni izlaz je potrebno ispisati T redova pri čemu je u i-tom redu potrebno ispisati faktorizaciju i-tog broja N sa ulaza. Činioce broja N ispisati u rastućem poretku i između svaka dva činioca ispisati znak '*' (zvezdica) bez razmaka i navodnika (videti dati primer).

Ograničenja
1 ≤ T ≤ 5.000
2 ≤ N ≤ 1.000.000.000.000
0 ≤ k ≤ 100Primer
Ulaz4
238 2
11 0
2431 0
10 1
Izlaz

2*7*17
11
11*13*17
2*5

Objašnjenje primera
Npr. u prvom paru (N = 238, k = 2), brojevi 2 i 7 su k-prosto udaljeni jer su oni prosti i između njih se nalaze tačno dva prosta broja: 3 i 5. Slično i za brojeve 7 i 17. Faktorizacija broja N pod navedenim uslovima je, naravno, jedinstvena.

Učitati dva broja i odrediti njihov NZD i NZS

Dat je niz prirodnih brojeva a od n elemenata. U jednom potezu dozvoljeno je odabrati proizvoljna dva susedna broja u nizu i zameniti ih njihovim zbirom. Na primer, ukoliko smo odabrali brojeve ai i ai + 1, niz (a1, a2, ..., ai, ai + 1, ... an) postaje (a1, a2, ..., ai + ai + 1, ... an). Ovo zatim možemo ponavljati na novodobijenim nizovima (primetimo da se broj elemenata niza svaki put smanjuje za 1).
Primeniti određeni broj poteza nad početnim nizom, tako da na kraju dobijemo tačno k brojeva čiji je najveći zajednički delilac najveći moguć.Ulaz
U prvom redu standardnog ulaza nalaze se 2 prirodna broja n i k koji predstavljaju, redom, broj elemenata u početnom nizu i broj elemenata koji treba ostati na kraju. Sledeći red sadrži n prirodnih brojeva ai (razdvojenih razmakom) koji predstavljaju početni niz.

Izlaz
U prvom redu standardnog ispisati maksimalni moguć najveći zajednički delilac preostalih brojeva. U drugom redu ispisati kprirodnih brojeva razdvojenih razmakom - izgled niza nakon svih poteza, čiji je najveći zajednički delilac maksimalan. Ukoliko ima više rešenja, štampati bilo koje.

Ograničenja
1 ≤ k < n ≤ 100.000
1 ≤ ai ≤ 1.000.000
Suma svih elemenata niza a nije veća od 1.000.000.Primer
Ulaz
6 3
12 7 3 2 15 15

Izlaz
6
12 12 30
Objašnjenje primera
Ukoliko izvršimo poteze (12, 7, 3, 2, 15, 15) → (12, 10, 2, 15, 15) → (12, 10, 2, 30) → (12, 12, 30) dobijamo brojeve 12, 12 i 30 čiji je najveći zajednički delilac jednak 6. Nije moguće dobiti 3 broja sa većim najvećim zajedničkim deliocem.

Dato je n prirodnih brojeva A1, A2, ..., An i m prirodnih brojeva B1, B2, ..., Bm. Potreno je izračunati NZD( A1 · A2 ··· An, B1 · B2 ··· Bm). Međutim, kako ovaj broj može biti jako veliki, izračunajte samo njegov ostatak pri deljenju sa 1.000.000.000.Ulaz
U prvom redu standardnog ulaza nalazi se jedan prirodan broj n. U drugom redu se nalaze n prirodnih brojeva - A1, A2, ..., An, razdvojeni razmakom. U trećem redu se nalazi prirodan broj m. U četvrtom redu se nalaze m prirodnih brojeva - B1, B2, ..., Bm, razdvojeni razmakom.

Izlaz
U prvi i jedini red standardnog izlaza ispisati ostatak pri deljenju traženog NZD-a brojem 1.000.000.000.

Ograničenja
1 ≤ n, m ≤ 1.000
1 ≤ Ai, Bi < 1.000.000.000

Primer
Ulaz3
358572 83391967 82
3
50229961 1091444 8863
Izlaz
12028

Objašnjenje primera
Važi NZD(358572 · 83391967 · 82, 50229961 · 1091444 · 8863) = NZD(2451966000072168, 485897929014301292) = 408661000012028. Kako je 408661000012028 MOD 1.000.000.000 = 12028, taj broj je rešenje.

Pretpostavimo da su internet adrese predstavljene prirodnim brojevima (IP adrese se, na primer, čuvaju u obliku neoznačenih 32-bitnih brojeva). Pretraživač čuva spisak svih adresa koje je korisnik posetio tokom nekog prethodnog perioda. Korisnik je mnoge adrese posećivao i više puta. Napiši program koji odrećuje broj različitih adresa koje je korisnik posetio.
Ulaz:
Sa standardnog ulaza se unosi broj n (1 ≤ n ≤ 10^5), a zatim i n prirodnih brojeva (manjih od 2^32),
svaki u posebnom redu.

Izlaz:
Na standardni izlaz ispisati broj različitih adresa koje je korisnik posetio.

Primer
Ulaz
8
123456789
234567890
345678901
234567890
456789012
234567890
456789012
234567890

U prodavnici se nalazi puno vrsta proizvoda i poznati su njihovi bar-kodovi. Proizvođač želi da sazna koliko se vrsta njegovih proizvoda prodaje u toj prodavnici. Ako je spisak svih kodova proizvoda u prodavnici dat u sortiranom obliku, a spisak svih kodova proizvoda proizvođača je dostavljen nesortiran, napiši program koji određuje traženi broj.
Ulaz:
Sa standardnog ulaza učitava se broj n (1 ≤ n ≤ 50000), a n prirodnih brojeva (najviše šestocifrenih), razdvojenih razmacima. Ti brojevi predstavljaju bar-kodove proizvoda u prodavnici i sortirani su rastuće. Nakon toga se do kraja ulaza učitavaju bar-kodovi proizvoda koje je proizvođač dostavio (najviše šestocifreni prirodni brojevi, svaki u posebnom redu).
Izlaz:
Na standardni izlaz ispisati broj proizvoda proizvođača koji se već prodaju u prodavnici.
Primer
Ulaz
5
1 3 5 6 7
2
3
4
5
8
Izlaz
2