Assuming that you mean, that we have to maximize the length of subarray such that it's sum is not divisible by $$$x$$$. Here is an approach I thought of for your second problem.

We consider the entire array, and if the sum is divisible by $$$x$$$, then search from both start and the end to find the first number that is not a multiple of $$$x$$$, choose to remove elements from the side which minimizes the length of the array the least.

For example consider, $$$x = 10$$$ and the array to be $$$A = [10, 20, 34, 55, 49, 32, 30]$$$. We first choose the entire array, then we get the sum to be $$$230$$$, now we see that it is divisible by $$$x$$$ so we search from the start and from the end for the element that is not divisible by $$$x$$$. So, from the start the third element $$$34$$$ is such an element, and from the end the second element from last that is $$$32$$$ is one such element. Since, if we remove the prefix, we will end up decreasing the length by 3 and if we remove suffix we will reduce the length by 2. So, we'll prefer suffix (since it minimizes the length by the least).

I cannot prove that this works, but I think it should, counter examples are always appreciated.

• Another approach to problem 2 can be like->

We create prefix sum of array in such a manner:

prefixsum[i] = ( prefixsum[i-1] + a[i] ) % x

Hence, the prefix_sum array would have values in the range [0,x-1].

Now, we iterate on the prefix_sum array and if we are currently at index i, and if we want to consider maximum length subarray ending at i and starting at index j+1 then we would need to find an index (j<i) such that

prefixsum[j] != prefixsum[i]

which would guarantee that prefixsum[i]-prefixsum[j] is not a multiple of x and hence the subarray sum from index j+1 to i is not divisible by x.

So, to find j we can the following logic:

1. If prefixsum[i] != 0, then j+1 = 0 hence max length subarray would be from 0 to i.

2. If prefixsum[i] = 0, then we just need the least index such that prefixsum[j] != 0 that can be easily pre-calculated.

define dp[i] as the length of the longest subarray ending at index i.

keep a variable div which stores the product of some factors of x taken from the current subarray. The took array tracks which factor was taken from each position.

For each element, we pick a factor of x that divides it, update div, and store that factor in took[i].

If div becomes divisible by x, we move the left end (j) forward and remove factors until div is no longer divisible by x.

Then, dp[i] = i - j + 1. After checking all positions, the maximum value in dp is our answer.

#include<bits/stdc++.h>
#define cb(x) __builtin_popcountll(x)
#define ctz(x) __builtin_ctzll(x)
#define clz(x) __builtin_clzll(x)
#define int long long
#define ll long long
#define pb push_back
#define debug(x) cout<<"Debug: "<<x<<endl;
using namespace std;

int mpow(int a,int b,int m){int x=1;while(b>0){if(b&1){x=((ll)x*a)%m;}a=((ll)a*a)%m;b>>=1;}return x;}
int mdiv(int a,int b, int m){int bin=mpow(b,m-2,m);return ((ll)a*bin)%m;}
int fact(int n,int m){if(n<=0) return 1;return ((ll)n*fact(n-1,m))%m;}
int nCr(int n,int r,int m){if(r==0)return 1;int ans=fact(n,m);ans=mdiv(ans,fact(n-r,m),m);ans=mdiv(ans,fact(r,m),m);return ans;}
int GCD(int a,int b){if(b==0)return a;return GCD(b,a%b);}

vector<int> divisors;
void getDivisors(int x){
    for(int i=1;i*i<=x;i++){
        if(x%i==0)divisors.pb(i);
        if(i*i!=x)divisors.pb(x/i);
    }
}
void solve(){
    int n,x;
    cin>>n>>x;
    int arr[n];
    for(auto &i:arr)cin>>i;
    divisors.clear();
    getDivisors(x);
    sort(divisors.begin(), divisors.end(),greater<int>());
    int div = 1;
    int dp[n];
    int took[n] = {1};
    for(auto &x:divisors){
        if(arr[0]%x == 0){
            div*=x;
            took[0] = x;
            break;
        }
    }
    int j = 0;
    if(div%x == 0)dp[0] = 0;
    else dp[0] = 1;

    for(int i=1;i<n;i++){
        for(auto &x:divisors){
            if(arr[i]%x == 0){
                div*=x;
                took[i]=x;
                break;
            }
        }
        while(div%x == 0){
            div/=took[j++];
        }
        dp[i] = i-j+1;
    }
    cout<<*max_element(dp,dp+n)<<endl;
}
int32_t main() {
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   int t;
   cin>>t;
   while (t--)
   {
       solve();
   }
    return 0;
}