#955 Miny Pbinfo
Fie N un număr natural nenul şi N numere naturale nenule: x1, x2,…, xN.
Fie P produsul acestor N numere, P=x1•x2•...•xN.
Cerinţe
Scrieţi un program care să citească numerele N, x1, x2,…, xN şi apoi să determine:
a) cifra zecilor produsului P;
b) cel mai mic număr natural Y, pentru care există numărul natural K astfel încât YK=P.
Date de intrare
Fișierul de intrare miny.in conţine două linii. Pe prima linie este scris numărul natural N. Pe următoarea linie sunt scrise cele N numere naturale x1, x2,…, xN, separate prin câte un spaţiu.
Date de ieșire
Fișierul de ieșire miny.out va conține:
pe prima linie o cifră reprezentând cifra zecilor produsului P;
pe a doua linie numărul natural M de factori primi din descompunerea în factori primi a numărului Y;
pe fiecare dintre următoarele M linii (câte o linie pentru fiecare factor prim din descompunere) câte două valori F şi E, separate printr-un singur spaţiu, F reprezentând factorul prim iar E exponentul acestui factor din descompunerea în factori primi a lui Y; scrierea în fişier a acestor factori primi se va face în ordinea crescătoare a valorii lor.
Restricții și precizări
2 ≤ N ≤ 50000
2 ≤ x1, x2,…, xN ≤ 10000
pentru rezolvarea corectă a cerinței a) se acordă 20% din punctaj iar pentru rezolvarea corectă a ambelor cerințe se acordă 100% din punctaj.
Exemplu 1
miny.in
6
12 5 60 25 4 36
miny.out
0
3
2 2
3 1
5 1
Explicație
Produsul celor 6 numere este: P=12∙5∙60∙25∙4∙36=12960000.
Cifra zecilor lui P este 0.
Se observă că există 3 valori posibile pentru Y: 12960000, 3600 şi 60 deoarece: 129600001=12960000, 36002=12960000, 604=12960000.
Cea mai mică valoare dintre aceste valori este 60, astfel Y=60=22*3*5.
Exemplu 2
miny.in
3
2 5 7
miny.out
7
3
2 1
5 1
7 1
Explicație
Produsul celor 3 numere este: P=2∙5∙7=70. Cifra zecilor lui P este 7. Există o singură valoare posibilă pentru Y: 70.
Răspunsuri la întrebare
#include <iostream>
#include <fstream>
using namespace std;
//gaseste cel mai mare divizor comun
int cmmdc(int a,int b){
int temp;
while(b>0){
temp=b;
b=a%b;
a=temp;
}
return a;
}
//pozitie in sir a divizorului prim
//daca nu se afla in sir, returneaza -1
int poz_in_sir(int div_prim[],int nr_div_prim,int x){
int i;
for(i=0;i<nr_div_prim;i++){
if(div_prim[i]==x){
return i;
}
}
return -1;
}
int main(){
int n,x,i,div,exp,k,div_prim[100],exp_prim[100],nr_div_prim=0,nr_exp_prim=0,prod=1;
ifstream fim("miny.in");
ofstream fom("miny.out");
fim>>n;
for(i=0;i<n;i++){
//citeste numar
fim>>x;
//in aflarea cifrei zecilor conteaza doar produsul ultimelor 2 cifre din fiecare numar
prod=(prod%100)*(x%100);
//primul nr prim este 2
div=2;
//cat timp x mai are factori
while(x>1){
//exponentul este 0 initial
exp=0;
//daca se imparte exact la div, mareste exponent
while(x%div==0){
exp++;
x=x/div;
}
//daca exponentul e mai mare ca 0, adica se imparte la div
if(exp>0){
//daca divizorul nu este in sir, adauga-l, cu tot cu exponent
if(poz_in_sir(div_prim,nr_div_prim,div)==-1){
div_prim[nr_div_prim]=div;
nr_div_prim++;
exp_prim[nr_exp_prim]=exp;
nr_exp_prim++;
}
//daca divizorul este deja in sir
//aduna exponentul gasit la exponentul deja existent
else{
exp_prim[poz_in_sir(div_prim,nr_div_prim,div)]+=exp;
}
}
div++;
}
}
//afla cifra zecilor produselor
prod=(prod%100)/10;
fom<<prod<<endl;
fom<<nr_div_prim<<endl;
k=exp_prim[0];
//k din formula este cel mai mare divizor comun
//dintre toti exponentii divizorilor primi
for(i=1;i<nr_exp_prim;i++){
k=cmmdc(exp_prim[i],k);
}
//puterile la y este exponentul impartit la cel mai mare divizor comun
for(i=0;i<nr_div_prim;i++){
fom<<div_prim[i]<<" "<<exp_prim[i]/k<<endl;
}
return 0;
}