题目

传送门

思路

可以发现我们对于每一个数，只需要将他的质因数的偶数次幂全部删去，之后判断两个数是否相同就可以判断两个数相乘是否为平方数

注意0这种特殊情况

代码

#include<iostream>
using namespace std;
int solve(int n)
{
    int f=1;
    if(n<0)
    {
        f=-1;
        n=-n;
    }
    for(int i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            int t=0;
            while(n%i==0)
            {
                n/=i;
                t++;
            }
            n*=max(1,i*(t%2));
        }
    }
    return n*f;
}
int n;
int a[5005];
int dp[5005];
int s[5005];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        a[i]=solve(a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        dp[i]=-1;
        for(int j=i-1;j>=1;j--)
        {
            if(a[i]==a[j])
            {
                dp[i]=j;
                break;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        int t=0;
        for(int j=i;j<=n;j++)
        {
            if(dp[j]<i&&a[j]!=0)
                t++;
            s[max(1,t)]++;
        }
    }
    for(int i=1;i<=n;i++)
        cout<<s[i]<<' ';
    return 0;
}

习题：Perfect Groups

原文：https://www.cnblogs.com/loney-s/p/12261487.html