Problem - 1470B - B. Strange Definition(质因数分解+思维)

题目大意:如果$a_i,a_j$满足$\frac{lcm(a_i,a_j)}{gcd(a_i,a_j)}$为一个完全平方数,那么就称这两个数相邻,在一秒过后,一个数$a_i$会变成所有和它相邻的数的积,求在某个时刻$t$时,相邻数字的最大个数.

解题思路:首先思考相邻的数满足的定义,我们分别将$a_i,a_j$拆分可得$a_i=2^{x_1}?3^{y_1}?5^{z_1}?...,a_i=2^{x_2}?3^{y_2}?5^{z_2}?...$;如果$a_i,a_j$相邻,那么一定满足$|x_1?x_2|,|y_1?y_2|,|z_1?z_2|$都是偶数.这样我们对每个$a_i$进行这样一次质因数分解,就可以得到一个数还需要哪些因子来变成完全平方数.我们再来思考秒数对答案的影响,如果允许进行乘的操作,那么那么已经相邻的数经过运算了之后还是相邻的数,而那些虽然相邻,但本身不是完全平方数的数,如果他们的个数是偶数,那么可以经过运算后变成完全平方数.然后取一个最大值即可.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define syncfalse ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int N = 3e5+5;
int a[N];void solve(){
    int n;cin>>n;map<int,int>s;for (int i = 1; i <= n; ++i)cin>>a[i];for (int i = 1; i <= n; ++i){
    int tem = a[i];int now = 1;for (int j = 2; j * j <= tem; ++j){
    if (tem%j==0){
    int num = 0;while(tem%j==0){
    tem/=j;num++;num%=2;}if (num)now*=j;}}now*=tem;s[now]++;}int maxd0 = 0;for (auto [x, y]: s){
    maxd0=max(maxd0, y);}int maxd1 = s[1];for (auto [x, y]: s){
    if (x==1)continue;if (y%2==0)maxd1+=y;}maxd1=max(maxd1, maxd0);int q;cin>>q;for (ll tem, i = 1; i <= q; ++i){
    cin>>tem;if (tem>0)cout << maxd1 << "\n";else cout << maxd0 << "\n";}
}int main(){
    syncfalse#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);#endifint t;cin>>t;for (;t;--t){
    solve();}return 0;
}