|
Sva pitanja, predloge ili primedbe u vezi sa takmičenjima iz programiranja
možete slati na e-mail:
tak.prog@gmail.com
U toku perioda za žalbe, sve žalbe možete slati na ovaj isti e-mail.
|
logo by Igor Antolović
|
|
|
zadatak: Faktorisanje
|
Dato je n brojeva. Potrebno je faktorisati svaki broj, tj. napisati ga kao proizvod prostih činioca.
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.
Ulaz.
(Ulazni podaci se učitavaju sa standardnog ulaza.)
U prvom redu standradnog ulaza nalazi se prirodan broj n ≤ 200.000. U sledećih n redova se
nalazi po jedan ceo broj bi koga treba faktorisati (2 ≤ bi ≤ 200.000).
Izlaz.
(Izlazne podatke ispisati na standardan izlaz.)
Na standardni izlaz za svaki broj ispisati u posebnom redu njegovu faktorizaciju u gore opisanom formatu,
u redosledu datim na ulazu.
Ograničenja.
U 40% test primera n ≤ 1.000
Primer 1.
standardni ulaz
|
|
standardni izlaz
|
3
10
23
180
|
|
2^1*5^1
23^1
2^2*3^2*5^1
|
|
|
fajl: faktorisanje.cpp
|
#include <cstdlib>
#include <cstdio>
const int MaxN = 200010;
const int MaxNum = 200000;
int n, num, p, exp, a[MaxN], leastDiv[MaxNum + 10];
bool prime[MaxNum + 10];
void eratosten(int N, bool prime[], int leastDiv[]) {
for (int i = 0; i <= N; i++)
prime[i] = true;
for (int i = 2; i <= N; i++) {
if (prime[i]) {
leastDiv[i] = i;
for (int j = 2; i * j <= N; j++)
if (prime[i * j]) {
prime[i * j] = false;
leastDiv[i * j] = i;
}
}
}
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
eratosten(MaxNum, prime, leastDiv);
for (int i = 0; i < n; i++) {
num = a[i];
while (num > 1) {
p = leastDiv[num];
exp = 0;
while (num % p == 0) {
exp++;
num /= p;
}
if (num > 1) printf("%d^%d*", p, exp);
else printf("%d^%d\n", p, exp);
}
}
return 0;
}
|
|
fajl: faktorisanje.pas
|
const
MaxN = 200010;
MaxNum = 200000;
var
n, num, p, exp, i : longint;
a : array[0..MaxN] of longint;
leastDiv : array[0..MaxNum + 10] of longint;
prime : array[0..MaxNum + 10] of boolean;
procedure eratosten(N : longint);
var
i, j : longint;
begin
for i := 0 to N do
prime[i] := true;
for i := 2 to N do
if (prime[i]) then begin
leastDiv[i] := i;
for j := 2 to N div i do
if (prime[i * j]) then begin
prime[i * j] := false;
leastDiv[i * j] := i;
end;
end;
end;
begin
readln(n);
for i := 1 to n do
readln(a[i]);
eratosten(MaxNum);
for i := 1 to n do begin
num := a[i];
while (num > 1) do begin
p := leastDiv[num];
exp := 0;
while (num mod p = 0) do begin
exp := exp + 1;
num := num div p;
end;
if (num > 1) then write(p, '^', exp, '*')
else writeln(p, '^', exp);
end;
end;
end.
|
|
|