If I am not wrong both can be solved using slight modifications to the Kadane's Algorithm

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.

bro why you use in the last div 3 round in problems D scanf & printf instead of use cin & cout like in other problems

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;
}