一道简单的 数论 题。

题目链接：CodeForces 980D。

题目

题目描述

对于一个长度为 $\text{len}$ 的序列 它的答案定义为最小划分的组数（以使得每个组中的数两两乘积为平方数)

给你一个长度为 $n(1\leq n \leq 5000)$ 的数组 $a _ i(-10^8\leq a _ i\leq 10^8)$。

对于其所有的子串，第 $k$ 个输出的数是答案为 $k$ 的子串的数量

数据范围

时空限制

题解

思路

考虑一个数 $a$，如果他满足：

$$\exists x\in\mathbb{P},x^2\mid a$$

那么我们可以直接把 $x^2$ 从 $a$ 中除掉，因为这根本不影响答案。

除去平方质因子后，不难发现，如果 $a$ 和 $b$ 能分在一组内当且仅当 $a=b$ 或 $a,b$ 其中一个是零。

所以枚举起点统计即可。

代码

时间复杂度为 $\Theta(n\log _ 2n+n^2)$

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg bool f=false;
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return f?-res:res;
}

const int MAXN=5000+5;
const int MAXSIZE=10000+5;

int tot,prime[MAXSIZE];
bool vis[MAXSIZE];

inline void Init(reg int n){
    for(reg int i=2;i<=n;++i){
        if(!vis[i])
            prime[++tot]=i;
        for(reg int j=1;j<=tot&&i*prime[j]<=n;++j){
            vis[i*prime[j]]=true;
            if(i%prime[j]==0)
                break;
        }
    }
    return;
}

int n;
int a[MAXN];
int pre[MAXN];
map<int,int> M;
int ans[MAXN];

int main(void){
    Init(1e4);
    n=read();
    for(reg int i=1;i<=n;++i){
        a[i]=read();
        if(a[i]!=0)
            for(reg int j=1;j<=tot;++j){
                reg int v=prime[j]*prime[j];
                if(a[i]%v==0)
                    while(a[i]%v==0)
                        a[i]/=v;
            }
    }
    memset(pre,-1,sizeof(pre));
    for(reg int i=1;i<=n;++i){
        if(M.find(a[i])!=M.end())
            pre[i]=M[a[i]];
        M[a[i]]=i;
    }
    for(reg int i=1;i<=n;++i){
        reg bool flag=false;
        reg int cnt=0;
        for(reg int j=i;j<=n;++j){
            if(a[j]!=0){
                if(pre[j]<i)
                    ++cnt;
            }
            else if(!flag){
                flag=true;
                ++cnt;
            }
            if(cnt==1&&flag)
                ++ans[1];
            else
                ++ans[flag?(cnt-1):cnt];
        }
    }
    for(reg int i=1;i<=n;++i)
        printf("%d%c",ans[i],i==n?'\n':' ');
    return 0;
}