E. Ehab's REAL Number Theory Problem

Link: E. Ehab's REAL Number Theory Problem

Description

You are given an array a of length n that has a special condition: every element in this array has at most 7 divisors. Find the length of the shortest non-empty subsequence of this array product of whose elements is a perfect square.

A sequence a is a subsequence of an array b if a can be obtained from b by deletion of several (possibly, zero or all) elements.

Input
The first line contains an integer n () — the length of a.

The second line contains n integers () — the elements of the array a.

Output
Output the length of the shortest non-empty subsequence of a product of whose elements is a perfect square. If there are several shortest subsequences, you can find any of them. If there's no such subsequence, print "-1".

Examples
input
3
1 4 6
output
1
input
4
2 3 6 6
output
2
input
3
6 15 10
output
3
input
4
2 3 5 7
output
-1
Note
In the first sample, you can choose a subsequence .

In the second sample, you can choose a subsequence .

In the third sample, you can choose a subsequence .

In the fourth sample, there is no such subsequence.

Problem solving

这道题的意思就是给你一组数，让你尽可能少的选择数，使得这些数的乘积为完全平方数。
every element in this array has at most 7 divisors，题目中的这句话很关键，说的是序列中的数最多有7个因子。
根据约数定理可得，如果一个数有三个质因子，那这个数最少有个因子。所以这句话的意思就是每个数最多有两个质因子.
并且我们可以发现，如果一个数对某个完全平方数取模为0，那么让这个数除以这个完全平方数对最后的答案没有影响。所以我们可以对所有数进行质因子分解，并且将质因子的幂对取模，这样就实现了除以某个完全平方数。
上面处理完之后，每个数只有三种情况

均为质数。如果出现了为的情况，那直接输出即可。因为你可以只选择这一个数。
接下来就是这个题最妙的地方。如果一个数处理完变成了，就把这两个数当成节点连接起来，如果处理完变成了，就把和连接起来。
这样会得到一个无向图，我们可以发现，如果有一个环存在，那么这个环中存在的那几个质因子相乘肯定是完全平方数。
所以这道题就变成了求无向图中的最小环。
直接暴力是肯定不行的，所以我们可以用求最小换，有两种方法可以优化。
一种是对质因子离散化，一种是遍历bfs的起点，从到。离散化就不用多说了。
这个为上界是因为如果起点的质因子大于，是不可能找到环的。因为肯定是大于的。

来找最小环，只要下一个点是被之前访问过的，更新的最小值即可,。和代表的是从当前的起点到和的距离，最后加的就是将和中间的那个距离。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+10;
const int inf =  0x3f3f3f3f;
vector<ll> V[maxn];
int dis[maxn],f[maxn];
int ans=inf; 
#define pb push_back
void bfs(int u) {
    memset(dis, inf, sizeof(dis));
    dis[u] = 0;
    queue<int> q;
    q.push(u);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < V[u].size(); i++) {
            int v = V[u][i];
            if (v != f[u]) {
                if (dis[v] != inf) ans = min(ans, (dis[u] + dis[v] + 1));
                else f[v] = u, dis[v] = dis[u] + 1, q.push(v);;
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    int n,x;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>x;
        int flag=0;
        for(int i=2;i<=sqrt(x);i++){
            while(x%(i*i)==0)    x/=i*i;
        }
        if(x==1){
            cout<<"1\n";
            return 0;
        }
        for(int i=2;i<=sqrt(x);i++){
            if(x%i==0){
                V[i].pb(x/i);
                V[x/i].pb(i);
                flag=1;
            }
        }
        if(!flag){
            V[1].pb(x);
            V[x].pb(1);
        }
    }
    for(int i=1;i<=sqrt(maxn);i++)    bfs(i);
    if(ans!=inf)    cout<<ans<<endl;
    else cout<<"-1"<<endl;
    return 0;
}
赏