[数论][图论][思维] codeforces 1325 E Ehab’s REAL Number Theory Problem

codeforces 1325 E

题意：给定一个长度1e5的数组$a$， $1 \le a_i \le 10^6$ ，满足 $a_i$的因子数量不超过7. 求 $a$ 的最短的满足所有元素相乘结果为完全平方数的子序列的长度。

这个题目做的时候。。一直在想怎么dp。。。完全没往图的方向想。太久没做题了就是这样，丢掉了很多东西，sigh

题解：

1. 首先可以把每个数字的平方因子去掉，非平方因子保留1次幂，答案不会受到影响，这是显然的。
2. 经过1的处理之后可以发现现在所有的数字都是1或者是一堆互不相同的素数之积。
3. 但是结合因子数量不超过7这个条件，我们可以发现其实剩下来的数字只有可能是 {1} {素数p} {素数p和素数q的乘积}，这三种情况，因为如果非1的素数因子个数超过2了那么必然至少有8个因子，与题意矛盾。（关键点1）
4. 这时候我们写一些会发现所有的满足要求的子序列，对于他们的素因子来说，都可以形成一个闭环。如果我们把不同的素数看作点，每一个 $a_i$ 看作一条边，那么此时要求的就是这个由数组 a 生成的不带权的无向图里的最小环。（关键点2）
5. 这个最小环可以用bfs来实现。拿一个点，也就是某个质数作为起点开始bfs，这样可以计算出来当前点所在的环里的最小环是多长。枚举每一个点然后bfs，就可以找到整个图形里的最小环，但是这样复杂度是 $O(n^2)$ ，因为我们这里的质数最多有n个，而边的数量也是n条，一条对应了一个 $a_i$ 。这样的话显然是会超时的
6. 但是这种找法其实是针对任意图的，我们这个图是由数字生成的，所以可能由更多的性质等待发现。思考一个问题：图上任意一条边，其两端每个点对应的质数不可能都超过 $sqrt(max(a_i))$，也就是每条边的两个端点必定有一个是小于等于 $sqrt(max(a_i))$ 的。这个证明起来是很容易的：如果有一条边两端不满足这个要求，那么这条边对应的 $a_i$ 就会大于 $max(a_i)$ ，矛盾。（关键点3）

于是便可只需搜索 $sqrt(max(a_i))$ 以内的所有质数，找环的复杂度变成了 $O(sqrt(max(a_i))*n)$，已经可以通过本题。如果想要更快可以把1e5的平方根内的所有质数先预处理出来，应该只有一两百个。

wa点：特判顺序写错了，一开始找到1或者2直接break了，其实只有1应该直接break。。因为找到2的话后面可能还有1。另外一点是处理 $a_i$ 时候写挫了一点，导致没有完全分解。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n,a[maxn],res[maxn][2],dis[maxn*10];
bool has[maxn*10];
char vis[maxn*10];
vector<int> g[maxn*10];

void d(int idx,int A){
    int cnt=0,top=0;
    if(!(A&1)){
        while(!(A&1)){
            A>>=1;
            ++cnt;
        }
        if(cnt&1) res[idx][top++]=2;
    }
    for(int i=3;i*i<=A;i+=2){
        cnt=0;
        while(A%i==0){
            A/=i;
            ++cnt;
        }
        if(cnt&1){
            res[idx][top++]=i;//error1 no break
        }
    }
    if(A!=1){
        res[idx][top++]=A;
    }
}

int bfs(int s){
    int res=n+1;
    queue<int> Q;Q.push(s);
    memset(vis,0,sizeof(vis));
    memset(dis,0,sizeof(dis));
    dis[s]=1;
    while(!Q.empty()){
        int cur=Q.front();Q.pop();
        vis[cur]=2;
        for(int v:g[cur]){
            if(vis[v]==2) continue;
            else if(vis[v]==1) res=min(res,dis[cur]+dis[v]-1);
            else{
                vis[v]=1;
                dis[v]=dis[cur]+1;
                Q.push(v);
            }
        }
    }
    return res;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    int maxA=1,flag1=0,flag2=0;
    for(int i=1;i<=n;++i){
        cin>>a[i],res[i][0]=res[i][1]=1,maxA=max(maxA,a[i]);
        d(i,a[i]);
        if(res[i][0]*res[i][1]==1){
            flag1=1;//no break
        }else if(has[res[i][0]*res[i][1]]){
            flag2=1;//no break
        }
        has[res[i][0]*res[i][1]]=1;
        g[res[i][0]].emplace_back(res[i][1]);
        g[res[i][1]].emplace_back(res[i][0]);
    }
    if(flag1) cout<<1,exit(0);
    if(flag2) cout<<2,exit(0);
    int ans=n+1;
    for(int i=sqrt(maxA)+1;i>=1;--i){
        ans=min(ans,bfs(i));
    }
    if(ans==n+1) cout<<-1;
    else cout<<ans;  
}