Advertisement
Guest User

Untitled

a guest
Apr 21st, 2021
4,656
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.80 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define MX 100000
  4. vector<int> p[100005];
  5. int a[100005],nex[100005],dp[20][100005];
  6. int main()
  7. {
  8.     int n,q;
  9.     scanf("%d%d",&n,&q);
  10.     for (int i=1;i<=n;i++)
  11.     scanf("%d",&a[i]);
  12.     for (int i=2;i<=MX;i++)
  13.     {
  14.         if (p[i].empty())
  15.         {
  16.             nex[i]=n+1;
  17.             for (int j=i;j<=MX;j+=i)
  18.             p[j].push_back(i);
  19.         }
  20.     }
  21.     dp[0][n+1]=n+1;
  22.     for (int i=n;i>0;i--)
  23.     {
  24.         dp[0][i]=dp[0][i+1];
  25.         for (int j:p[a[i]])
  26.         {
  27.             dp[0][i]=min(dp[0][i],nex[j]);
  28.             nex[j]=i;
  29.         }
  30.     }
  31.     for (int i=1;i<20;i++)
  32.     {
  33.         for (int j=1;j<=n+1;j++)
  34.         dp[i][j]=dp[i-1][dp[i-1][j]];
  35.     }
  36.     while (q--)
  37.     {
  38.         int l,r,ans=0;
  39.         scanf("%d%d",&l,&r);
  40.         for (int i=19;i>=0;i--)
  41.         {
  42.             if (dp[i][l]<=r)
  43.             {
  44.                 ans+=(1<<i);
  45.                 l=dp[i][l];
  46.             }
  47.         }
  48.         printf("%d\n",ans+1);
  49.     }
  50. }
  51.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement