Advertisement
Guest User

Untitled

a guest
Mar 14th, 2020
3,913
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.39 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define MX 1000000
  4. int lp[MX+5],dist[MX+5];
  5. vector<int> d[MX+5],v[MX+5],pr;
  6. vector<vector<int> > e;
  7. int main()
  8. {
  9.     pr.push_back(1);
  10.     for (int i=2;i<=MX;i++)
  11.     {
  12.         if (!lp[i])
  13.         {
  14.             pr.push_back(i);
  15.             for (int j=i;j<=MX;j+=i)
  16.             lp[j]=i;
  17.         }
  18.         d[i]=d[i/lp[i]];
  19.         auto it=find(d[i].begin(),d[i].end(),lp[i]);
  20.         if (it!=d[i].end())
  21.         d[i].erase(it);
  22.         else
  23.         d[i].push_back(lp[i]);
  24.     }
  25.     int n,ans=1e9;
  26.     scanf("%d",&n);
  27.     for (int i=0;i<n;i++)
  28.     {
  29.         int a;
  30.         scanf("%d",&a);
  31.         if (d[a].empty())
  32.         {
  33.             printf("1");
  34.             return 0;
  35.         }
  36.         if (d[a].size()==1)
  37.         d[a].push_back(1);
  38.         e.push_back({d[a][0],d[a][1]});
  39.         v[d[a][0]].push_back(i);
  40.         v[d[a][1]].push_back(i);
  41.     }
  42.     for (int i:pr)
  43.     {
  44.         if (i*i>MX)
  45.         break;
  46.         for (int j:pr)
  47.         dist[j]=0;
  48.         queue<pair<int,int> > q;
  49.         for (int j:v[i])
  50.         {
  51.             q.push({j,(e[j][0]==i)});
  52.             dist[e[j][0]^e[j][1]^i]=1;
  53.         }
  54.         while (!q.empty())
  55.         {
  56.             auto p=q.front();
  57.             q.pop();
  58.             int node=e[p.first][p.second];
  59.             for (int u:v[node])
  60.             {
  61.                 if (u!=p.first)
  62.                 {
  63.                     pair<int,int> np(u,(e[u][0]==node));
  64.                     int nnode=e[np.first][np.second];
  65.                     if (!dist[nnode] && nnode!=i)
  66.                     {
  67.                         q.push(np);
  68.                         dist[nnode]=dist[node]+1;
  69.                     }
  70.                     else
  71.                     ans=min(ans,dist[node]+dist[nnode]+1);
  72.                 }
  73.             }
  74.         }
  75.     }
  76.     if (ans==1e9)
  77.     ans=-1;
  78.     printf("%d",ans);
  79. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement