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.
Constraints
- 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.
Subtasks
Subtask #1 (100 points): Original constraints
Sample Input 1
3
3 3
3 3 3
4 4
1 2 3 4
4 54
36 81 54 54
Sample Output 1
6
1
6
Explanation
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 CodeRead More Post Here
