CodeForces - 1497E1 判断完全平方数质因数分解

本文主要是介绍CodeForces - 1497E1 判断完全平方数质因数分解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

https://vjudge.net/problem/CodeForces-1497E1

题意

给出数组，让你将他分为连续的ans段，使得每一段数组内的数字两两相乘不出现完全平方数，最小化ans。

思路

判断是否相乘得到完全平方数可以用以下方法：

我们将数x进行质因数分解，可以得到x=p1^q1 * p2^q2 …的形式，我们将q1，q2统统模二处理，得到 f(x)=p1^(q1%2) * p2^(q2%2) …容易发现，当且仅当f(x)==f(y)时，xy得到完全平方数。因此我们用map建立映射关系，扫描整个数组即可。

对x进行质因数分解最坏时间复杂度是O（sqrt（x）），当x为质数时复杂度最坏，如果我们用更快的筛法预处理出质数，那么可以加快质因数分解的速度。

代码

#include<cstdio>
#include<iostream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<string>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib> 
#include<chrono>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
//#define int long long
//#define double long double
using namespace std;typedef long long ll;const int maxn=200505;const int maxvalue=10000050;const int inf=0x3f3f3f3f;int n,m,k;struct custom_hash {static uint64_t splitmix64(uint64_t x) {x += 0x9e3779b97f4a7c15;x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;x = (x ^ (x >> 27)) * 0x94d049bb133111eb;return x ^ (x >> 31);}size_t operator()(uint64_t x) const {static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();return splitmix64(x + FIXED_RANDOM);}};int prime[maxvalue],cnt;bool is[maxvalue];void init(int x){for(int i=2;i<=x;i++){if(!is[i]) prime[++cnt]=i;for(int j=1;prime[j]<=n/i;j++){is[prime[j]*i]=1;if(i%prime[j]==0) break;}}}int trans(int x){int rec=1;if(is[x])   return x;for(int i=2;i*i<=x;i++){int cnt=0;while(x%i==0){x/=i;cnt++;}if(cnt%2){rec*=i;}}if(x>1) rec*=x;return rec;}signed main(){IOS#ifndef ONLINE_JUDGEfreopen("IO\\in.txt","r",stdin);freopen("IO\\out.txt","w",stdout);#endifinit(maxvalue);int tn;cin>>tn;while(tn--){cin>>n>>m;int ans=1;unordered_map<int,bool,custom_hash>mp;for(int i=1;i<=n;i++){int t;cin>>t;t=trans(t);cout<<t<<' ';if(mp[t]){mp.clear();ans++;mp[t]=1;}elsemp[t]=1;}cout<<endl;cout<<ans<<endl;}}