Count of subarrays having product as a perfect cube | C ++ program for the above approach ; Function to store the prime factorization of a number ; If N is divisible by i ; Increment v [ i ] by 1 and calculate it modulo by 3 ; Divide the number by i ; If the number is not equal to 1 ; Increment v [ n ] by 1 ; Calculate it modulo 3 ; Function to count the number of subarrays whose product is a perfect cube ; Store the required result ; Stores the prime factors modulo 3 ; Stores the occurrences of the prime factors ; Traverse the array , arr [ ] ; Store the prime factors and update the vector v ; Update the answer ; Increment current state of the prime factors by 1 ; Print the result ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  1e5 NEW_LINE void primeFactors ( vector < int > & v , int n ) { for ( int i = 2 ; i * i <= n ; i ++ ) { while ( n % i == 0 ) { v [ i ] ++ ; v [ i ] %= 3 ; n /= i ; } } if ( n != 1 ) { v [ n ] ++ ; v [ n ] %= 3 ; } } void countSubarrays ( int arr [ ] , int n ) { int ans = 0 ; vector < int > v ( MAX , 0 ) ; map < vector < int > , int > mp ; mp [ v ] ++ ; for ( int i = 0 ; i < n ; i ++ ) { primeFactors ( v , arr [ i ] ) ; ans += mp [ v ] ; mp [ v ] ++ ; } cout << ans ; } int main ( ) { int arr [ ] = { 1 , 8 , 4 , 2 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; countSubarrays ( arr , N ) ; return 0 ; }