网站建设行业发展趋势,永久免费access进销存软件,北京中国建设银行招聘信息网站,网络媒体软文案例传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
给你nnn个数#xff0c;每个数的因子个数不超过777个#xff0c;选出最少的数使其乘积为平方数。 n≤1e5n\le 1e5n≤1e5
思路#xff1a;
由于因子不超过777个#xff0c;所以由约数个数(1p1)∗(1p2)∗…传送门
文章目录题意思路题意
给你nnn个数每个数的因子个数不超过777个选出最少的数使其乘积为平方数。 n≤1e5n\le 1e5n≤1e5
思路
由于因子不超过777个所以由约数个数(1p1)∗(1p2)∗...∗(1pn)(1p_1)*(1p_2)*...*(1p_n)(1p1)∗(1p2)∗...∗(1pn)得其质因子个数不超过222个启发我们用质因子来做这个题。 一个显然的性质就是平方数的质因子幂次mod2\bmod 2mod2之后这个平方数为111。所以我们将每个数的质因子幂次mod2\bmod 2mod2之后留下为幂次111的质因子。现在问题就变成了选出尽可能少的点使其乘积的质因子幂次为偶数考虑将其转换成图上的问题。 如果一个数本身就是平方数那么直接输出111就好啦下面讨论质因子个数不为000的情况。 先考虑每个数的质因子都有两个的情况考虑以质数为每个点将每个数的两个质因子连边那么画出来图之后可以发现最小环即为答案。 如果质因子只有一个怎么办呢考虑建立一个虚拟节点111将其与111连边之后跑最小环就好啦。 那么问题来了最小环FloydFloydFloyd显然是不可以的我们需要发现我们构建的图的一些特殊性质。 首先边权都为111且为无向图那么我们可以枚举起点遍历每条边记一个depthdepthdepth每当碰到的depthdepthdepth被更新过了那么ansmin(ans,depth[u]depth[v]1)ansmin(ans,depth[u]depth[v]1)ansmin(ans,depth[u]depth[v]1)即可但是复杂度是n2n^2n2的仍然不可接受。 继续考虑优化起点由于100010001000的质数不会相互连边所以只需枚举≤1000\le1000≤1000的质数即可复杂度nan\sqrt ana可以接受。
// Problem: E. Ehabs REAL Number Theory Problem
// Contest: Codeforces - Codeforces Round #628 (Div. 2)
// URL: https://codeforces.com/contest/1325/problem/E
// Memory Limit: 256 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n;
int a[N];
int e[N],ne[N],h[N],idx;
int prime[N],cnt,ansINF;
int depth[N];
bool st[N];
vectorintv;void add(int a,int b) {e[idx]b,ne[idx]h[a],h[a]idx;
}void divide(int x) {int a,b; ab-1;for(int i2;ix/i;i) {if(x%i0) {int cnt0;while(x%i0) x/i,cnt;if(cnt%20) continue;if(a-1) ai;else if(b-1) bi;}}if(x1) {if(a-1) ax;else bx;}if(a-1) {puts(1);exit(0);}if(b-1) add(1,a),add(a,1);else add(a,b),add(b,a);
}void get_prime(int n) {for(int i2;in;i) if(!st[i]) {for(int jii;jn;ji) st[j]1;prime[cnt]i;}
}void bfs(int st) {queueintq1,q2;memset(depth,-1,sizeof(depth));q1.push(st); q2.push(-1);depth[st]0;while(q1.size()) {int aq1.front(); q1.pop();int bq2.front(); q2.pop();for(int ih[a];~i;ine[i]) {int je[i];if((i^1)b) continue;if(depth[j]-1) depth[j]depth[a]1,q1.push(j),q2.push(i);else ansmin(ans,depth[a]depth[j]1);}}
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);get_prime(2000);memset(h,-1,sizeof(h));scanf(%d,n);for(int i1;in;i) {scanf(%d,a[i]);divide(a[i]);}for(int i1;icnt;i) bfs(i);printf(%d\n,ansINF? -1:ans);return 0;
}
/**/
