Codeforces 1235E Ehab's REAL Number Theory Problem 题解

发表于 | 阅读次数：
本文字数： 1.5k 字 | 阅读时长 ≈ 7 分钟

考场上想出了思路，但是没能写出来代码，实在可惜

题意简述

有 $n\le 1e5$ 个正整数，每个数值域都是 $[1,10^6]$，并且最多有 $7$ 个因数。 请你求出最少选多少个数能使得乘积是平方数。

思路

最多 $7$ 个因数 $\leftrightarrow$ 最多两个质因数

而且对于一个质因数，显然我们还可以把它的指数膜个 $2$。如果指数到最后是 $0$，那么我们直接扔掉这个质因数；如果两个质因数指数都是 $0$，那好了，直接输出 $1$，结束程序。

然后就是一个数等于 $p$ 或者 $p\times q$ 的情况了。$p$ 的情况就加边 $(1,p)$，$p\times q$ 的情况就加边 $(p,q)$，然后求一个最小环即可。 而且我们发现，一个环上顶多有一个点在 $>1000$ ，那么我们可以以 $1~1000$ 中的点为起点，分别使用 $BFS$ 找环法。这样只能找到包含某个点的最小环，但这足够了，因为这个环必然包含一个编号小于等于 $1000$ 的点。而我们只会在质数间连边，所以我们的实际复杂度比你想象的要小很多！

怎么想到的

主要就是如何转换为最小环那一步。首先这个相当于我们选若干个数，分解成 $1\times p$ 或者 $p\times q$ 的形式，然后几个数覆盖起来，每个质数 $p$ 都得被算偶数次（$0$ 也是偶数，不算到也是可以的）。那这样我们的总乘积中，每个质因数都是偶数次方，那就是完全平方数了。

考虑到一个简单的环上的每个点度数都是 $2$，所以我们就能想到把它建成图，然后跑最小环。那么有小朋友（无 中 生 友）就问了，会不会有环上的点度数为 $4,6,8$，甚至更大的偶数呢？其实这个就相当于一个点被算了很多次嘛，但是我们要求的是“最少多少个数的积是平方数”，也就是我们要让环尽量的小。容易证明，一个最小的环肯定是简单环。（因为如果你是一个复合的环，那么肯定能拆出来若干的简单环，答案更优）

代码

点击
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 1666666
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    #define Tra(i,u) for(int i=G.Start(u),v=G.To(i);~i;i=G.Next(i),v=G.To(i))
    #define p_b push_back
    #define sz(a) ((int)a.size())
    #define iter(a,p) (a.begin()+p)
    int I()
    {
        int x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        return (x=(f==1)?x:-x);
    }
    void Rd(int cnt,...)
    {
        va_list args; va_start(args,cnt);
        F(i,1,cnt) {int* x=va_arg(args,int*);(*x)=I();}
        va_end(args);
    }
    class Graph
    {
        public:
            int head[N];
            int EdgeCount;
            struct Edge
            {
                int To,Next;
            }Ed[N<<1];
            void clear(int _V=N,int _E=N<<1) 
            {
                memset(Ed,-1,sizeof(Edge)*(_E));
                memset(head,-1,sizeof(int)*(_V));
                EdgeCount=-1;
            }
            void AddEdge(int u,int v)
            {
                Ed[++EdgeCount]=(Edge){v,head[u]};
                head[u]=EdgeCount;
            }
            void Add2(int u,int v) {AddEdge(u,v);AddEdge(v,u);}
            int Start(int u) {return head[u];}
            int To(int u){return Ed[u].To;}
            int Next(int u){return Ed[u].Next;}
    }G;
    
    bool notp[N]; int primes[N];;
    vector<int> pd[N];
    //prime divisors 的简写，保存质因数
    void Init()
    {
        notp[1]=1;
        int n=1e6;
        F(i,2,n) if (!notp[i]) 
        {
            primes[++primes[0]]=i;
            pd[i].p_b(i);
            Fs(j,2*i,n,j+=i) 
            {
                if (sz(pd[j])<2) pd[j].p_b(i);  
                notp[j]=1;
                // 题目保证质因数个数<=2，只要存前两个即可，空间复杂度O(2n)
            }
        }
        
    }
    int n,a[N];
    void Input()
    {
        n=I(); F(i,1,n) a[i]=I();
        sort(a+1,a+n+1);
    }

    int  cnt(int p,int x) //计算 x 有多少个因子 p
    {
        int ans=0; 
        while(x%p==0) {ans^=1; x/=p;}
        return ans;
    }

    int ans=0x3f3f3f3f;
    bool added[N]; // 判一下重边
    void add(int a,int b)
    {
        if (added[a*b]) {ans=min(ans,2); return;} //有重边，那就能组成一个二元环，答案更新为 2
        added[a*b]=1; G.Add2(a,b);
    }
    void Factor(int x)
    {
        if (x==1) {puts("1"); exit(0);}
        if (sz(pd[x])==1)
        {
            int p=pd[x][0],pp=cnt(p,x);
            if (pp==0) {ans=min(ans,1);}
            else {add(1,p);}
        }
        else //pd[x].size()==2
        {
            int p=pd[x][0],q=pd[x][1];
            int pp=cnt(p,x),qq=cnt(q,x);
            if (pp==0 and qq==0) {ans=min(ans,1);}
            else if (pp==1 and qq==1) {add(p,q);}
            else if (pp==0 and qq==1) {add(1,q);}
            else if (pp==1 and qq==0) {add(1,p);}
        }
    }
    int Q[N],vis[N],dis[N],fa[N]; int Round=0;
    void BFS(int s) // 包含 s 的最小环
    {
        int head=1,tail=1;
        ++Round; 
        Q[tail]=s; dis[s]=0;
        while(head<=tail)
        {
            int u=Q[head++];
            vis[u]=Round;
            Tra(i,u) 
            {
                if (vis[v]!=Round) {dis[v]=dis[u]+1; vis[v]=Round; Q[++tail]=v; fa[v]=u;}
                else 
                {
                    if (v!=fa[u]) ans=min(ans,dis[u]+dis[v]+1);
                    // 此时 s->u,u->v,v->s 组成一个环，三个部分长度分别是 dis[u],1,dis[v]，总长度就是 dis[u]+dis[v]+1
                    // 注意不能搜回前驱节点
                }
            }
        }
    }
    void Soviet()
    {
        G.clear(); 
        F(i,1,n) Factor(a[i]);
        if (ans<=2) {printf("%d\n",ans); return;}
        BFS(1); F(i,1,180) BFS(primes[i]);
        printf("%d\n",ans==0x3f3f3f3f?-1:ans);
    }

    #define Flan void
    Flan IsMyWife()
    {
        Init();
        Input();
        Soviet();
    }
}
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}
w