Kostomuksha and AESC MSU Codechef Solution | MARCH CHALLENGE


Kostomuksha and AESC MSU Codechef Solution

A famous student of AESC MSU, as you know, comes from Kostomuksha. Kostomuksha has a popular game called Doka.

The essence of Doka is as follows:

You are given an array AA and an integer XX. You want to calculate how many subarrays of this array have a geometric mean of XX.

Formally, calculate the number of pairs of integers (L,R)(L,R) such that 1≤L≤R≤N1≤L≤R≤N andAL⋅AL+1⋅…⋅AR−−−−−−−−−−−−−−−√R−L+1=XAL⋅AL+1⋅…⋅ARR−L+1=X

Input Format

  • The first line of input contains an integer TT, denoting the number of test cases. The description of TT test cases follows.
  • Each test case consists of two lines of input.
  • The first line of each test case contains two space-separated integers N,XN,X — the size of the array AA and the required geometric mean.
  • The second line of each test case contains NN space-separated integers A1,A2,…,ANA1,A2,…,AN.

Output Format

For each test case, on a new line print the number of subarrays that satisfy the condition.


  • 1≤T≤1031≤T≤103
  • 1≤N≤2⋅1051≤N≤2⋅105
  • 1≤X,Ai≤1091≤X,Ai≤109
  • Sum of NN over all test cases does not exceed 2⋅1052⋅105.


Subtask #1 (100 points): Original constraints

Sample Input 1 

3 3
3 3 3
4 4
1 2 3 4
4 54
36 81 54 54

Sample Output 1 



Test case 11: Every subarray has a geometric mean of 33, and there are 66 subarrays in total so the answer is 66.

Test case 22: The only subarray with a geometric mean of 44 is the singleton array [4][4], obtained with L=R=4L=R=4.

Test case 33: The 66 pairs of (L,R)(L,R) which have a geometric mean of 5454 are:

  • (1,2)(1,2), giving the subarray [36,81][36,81]
  • (1,3)(1,3), giving the subarray [36,81,54][36,81,54]
  • (1,4)(1,4), giving the subarray [36,81,54,54][36,81,54,54]
  • (3,3)(3,3), giving the subarray [54][54]
  • (3,4)(3,4), giving the subarray [54,54][54,54]
  • (4,4)(4,4), giving the subarray [54]

Kostomuksha and AESC MSU Codechef  SOLUTION

Download Code

Read More Post Here

Leave a Comment

Your email address will not be published. Required fields are marked *