Question

Se dă un şir cu n numere naturale nenule care sunt divizibile doar cu numerele prime 2, 3 sau 5. Determinaţi numărul secvenţelor din şir pentru care produsul elementelor este pătrat perfect.

Date de intrare
Fișierul de intrare produs3.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale nenule divizibile doar cu numerele prime 2, 3 sau 5, separate prin spații.

Date de ieșire
Fișierul de ieșire produs3.out va conține pe prima linie numărul S, reprezentând numărul secvenţelor din şir pentru care produsul elementelor este pătrat perfect.

Restricții și precizări
1 ≤ n ≤ 1.000.000
numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000



Exemplu
produs3.in

5
12 3 4 5 45
produs3.out

6
Explicație
În şirul dat sunt 6 sevenţe pentru care produsul elementelor este pătrat perfect:

12 , 3
12 , 3 , 4
4
5 , 45
4 , 5 , 45
12 , 3 , 4 , 5 , 45

Answer 1

Programul afiseaza toate secventele posibile in outputul ferestrei
#include <iostream>
#include <fstream>
using namespace std;
int divizori[300];

int main(){
int n,i,k=0,j,temp,v[100],nr=0,div2,div3,div5;
ifstream fin("produs3.in");
ofstream fou("produs3.out");
fin>>n;
for(i=0;i<n;i++){
fin>>v[i];
temp=v[i];
while(temp%2==0){
divizori[3*i]++;
temp=temp/2;

}
temp=v[i];
while(temp%3==0){
divizori[3*i+1]++;
temp=temp/3;
}
temp=v[i];
while(temp%5==0){
divizori[3*i+2]++;
temp=temp/5;
}
}
while(k<n){
div2=0;
div3=0;
div5=0;
for(i=k;i<n;i++){
div2=div2+divizori[3*i];
div3=div3+divizori[3*i+1];
div5=div5+divizori[3*i+2];
if(div2%2==0&&div3%2==0&&div5%2==0){
nr++;
for(j=k;j<=i;j++){
cout<<v[j]<<" ";
}
cout<<endl;
}
}
k++;
}
fou<<nr;
return 0;
}