Advertisement
YEZAELP

CUBE-169: Factor Match

Aug 9th, 2020
104
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.36 KB | None
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using lli = long long;
  5. const lli INF = 2e18;
  6. const lli PB = 98765431;
  7.  
  8. lli ar[1000001], compare[1000001], f[100001];
  9.  
  10. lli factor(lli n){
  11.     if(f[n] != 0) return f[n];
  12.     for(int i=1;i<=sqrt(n);i++){
  13.         if(n%i == 0) {
  14.             if(n/i == i) f[n]++;
  15.             else f[n] += 2;
  16.         }
  17.     }
  18.     return f[n];
  19. }
  20.  
  21. int main(){
  22.  
  23.     int n,m;
  24.     scanf("%d%d",&n,&m);
  25.     for(int i=1;i<=n;i++){
  26.         scanf("%lld",&ar[i]);
  27.         ar[i] = factor(ar[i]);
  28.     }
  29.     for(int i=1;i<=m;i++){
  30.         scanf("%lld",&compare[i]);
  31.         compare[i] = factor(compare[i]);
  32.     }
  33.  
  34.     int mx = 0, l = 1, r = m, mid;
  35.     while(l <= r){
  36.         mid = (l+r)/2;
  37.         bool found = false;
  38.         lli rem = 1, cmp = 0, hsh = 0;
  39.         for(int i=1;i<=mid;i++){
  40.             if(i != 1) rem = rem*PB;
  41.             cmp = cmp*PB + compare[i];
  42.             hsh = hsh*PB + ar[i];
  43.         }
  44.         for(int i=1;i<=n-m+1;i++){
  45.             if(i != 1) hsh = hsh*PB + ar[i+mid-1];
  46.             if(cmp == hsh) {
  47.                 found = true;
  48.                 break;
  49.             }
  50.             hsh = hsh-rem*ar[i];
  51.         }
  52.  
  53.         if(found){
  54.             l = mid + 1;
  55.             mx = max(mx,mid);
  56.         }
  57.         else {
  58.             r = mid - 1;
  59.         }
  60.     }
  61.  
  62.     printf("%d",mx);
  63.  
  64.     return 0;
  65. }
  66.  
Advertisement
RAW Paste Data Copied
Advertisement