Odd Number of Divisors - De Shaw MNIT Jaipur

Problem Preview

"### Problem Statement You are given an array A of N positive integers. The product of a subarray is said to be special if it has an odd number of positive divisors. Count the number of contiguous subarrays whose product is special. ### Input Format - The first line contains an integer N. - The second line contains N integers A1, A2, ..., AN. ### Output Format Print a single integer — the number of special subarrays. ### Constraints - 1 ≤ N ≤ 2 × 10^5 - 1 ≤ Ai ≤ 10^9 ### Sample Input 5 1 4 2 9 16 ### Sample Output 6 ### Explanation A number has an odd number of divisors if and only if it is a perfect square. The qualifying subarrays are: - [1] - [4] - [9] - [16] - [1, 4] - [4, 2, 9, 16] Hence, the answer is 6."