CUBE-T169: Factor Match

#include <bits/stdc++.h>
using namespace std;

typedef long long lli;
typedef pair<int, int> pii;

const int X = 1e5;
const int sqrtX = sqrt(X);
const int N = 1e6;
const int PB = 1e9 + 7;

int arrA[N + 1], arrB[N + 1], minDiv[X + 1], factorCnt[X + 1];
int lenA, lenB;

int factor(int x){
    int lastOne = 1;
    int cnt = 0;
    int ans = 1;
    while(true){
        if(minDiv[x] != lastOne){
            ans *= cnt + 1;
            lastOne = minDiv[x];
            cnt = 1;
        } else {
            ++cnt;
        }
        if(x == 1){
            break;
        }
        x /= minDiv[x];
    }
    return ans;
}

bool sameSubstr(int len){
    lli hshTr = 0;
    lli base = 1;
    for(int i = 1; i <= len; ++i){
        if(i > 1){
            base *= PB;
        }
        hshTr *= PB;
        hshTr += arrB[i];
    }
    lli hsh = 0;
    for(int i = 1; i <= len; ++i){
        hsh *= PB;
        hsh += arrA[i];
    }
    if(hsh == hshTr){
        return true;
    }
    for(int i = len + 1; i <= lenA - lenB + len; ++i){
        hsh -= base * arrA[i - len];
        hsh *= PB;
        hsh += arrA[i];
        if(hsh == hshTr){
            return true;
        }
    }
    return false;
}

int main(){

    // Sieve
    minDiv[1] = 0;
    for(int i = 2; i <= X; ++i){
        if(minDiv[i] == 0){
            for(int j = i; j <= X; j += i){
                minDiv[j] = i;
            }
        }
    }

    // Precompute factors
    for(int i = 1; i <= X; ++i){
        factorCnt[i] = factor(i);
    }

    scanf("%d%d", &lenA, &lenB);
    for(int i = 1; i <= lenA; ++i){
        int x;
        scanf("%d", &x);
        arrA[i] = factorCnt[x];
    }
    for(int i = 1; i <= lenB; ++i){
        int x;
        scanf("%d", &x);
        arrB[i] = factorCnt[x];
    }

    int l = 0;
    int r = lenB;
    int mx = 0;
    while(l <= r){
        int m = (l + r) / 2;
        if(sameSubstr(m)){
            mx = max(mx, m);
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    cout << mx;

    return 0;
}