Help Needed in array based problem

Given T testcases each testcase consists of an array A[] of length N. Now for each array we have to count the no. of subarrays such that sum of elements of the subarray is divisible by each individual element of the subarray.

Here 1<=T<=100 , 1<=N<=2000 and A[i]<=10^9.

My approach: I am computing the sum and LCM of each subarray and then checking if sum of subarray is divisible by LCM with time complexity of O(TN^2log(n)) but getting TLE. Here log(n) comes from the gcd() function required for computing LCM.Please suggest some optimizations or some other approach for this problem. Thanks in advance.

This can be done in O(n^2).
Use prefix sum array for calculating sum of every subarray and use prefix product array and gcd matrix for every subarray.
Sum for subarray$[i, j]$ can be calculated as sum_{ij} = prefsum[j] - prefsum[i].
Similarly, lcm for subarray$[i, j]$ can be calculated as prod_{ij} = \frac{prod[j]}{prod[i]} where prod[i]!=0 and gcd_{ij} = gcd[i][j]
lcm_{ij} = \frac{prod_{ij}}{gcd_{ij}}
Then for every subarray you can calculate the sum in O(1) and lcm in O(1), and then check if is lcm divides the sum.

1 Like

Here each array element is less than 10^9 so how is prefix product array possible as it can cause overflow here.

1 Like

even if id didnt time out,it would’ve probably give wa,as lcm could exceed the range of long int,

try finding lcm of

2,3,5,7,9,…2000th prime

Can you suggest some other approach??

Ur approach is almost correct,just a few corrections

See since each element <=10^9

Sum <=10^12

so if ur lcm exceeds 10^12 ,there’s no chance that Sum would be divisible

pseudo code:

for i in range(1,n+1):
     sum=0,lcm=1
     for j in range(i,n+1):
          sum=sum+a[j]
          lcm=lcm*a[j]/(gcd(lcm,a[j]))
          if(lcm is greater than 10^12)
               break
          if(sum is greater than or equal to lcm):
              if(sum%lcm==0)res++

I dont think so gcd should affect that much,if it do tell me,u could use the inbuilt gcd functions(i use them in c++)

And try to minimise % operations,use fast io

2 Likes

Can you please post the link to the question where you are solving this.

Now getting wrong answer. Can you please check my implementation https://ideone.com/oBl0hX

https://ide.geeksforgeeks.org/UYgicvh8eO

overflow mostly,try this,and if possible provide link to the question

Getting wrong answer.
Link to problem: http://codeforces.com/gym/101498/problem/G

Link to problem: http://codeforces.com/gym/101498/problem/G

Got Accepted using unsigned long int

https://ide.geeksforgeeks.org/v5taDx7yop

Even using long long it gets accepted,see this just some modifications to ur code