一道简单的 数论 题。
题目链接:CodeForces 980D。
题目
题目描述
对于一个长度为 $\text{len}$ 的序列 它的答案定义为最小划分的组数(以使得每个组中的数两两乘积为平方数)
给你一个长度为 $n(1\leq n \leq 5000)$ 的数组 $a _ i(-10^8\leq a _ i\leq 10^8)$。
对于其所有的子串,第 $k$ 个输出的数是答案为 $k$ 的子串的数量
数据范围
变量 | 数据范围 |
---|---|
$n$ | $1\leq n\leq 5000$ |
$a$ | $-10^8\leq a\leq 10^8$ |
时空限制
题目编号 | 时间限制 | 空间限制 |
---|---|---|
CodeForces 980D | $1\text{s}$ | $256\text{MiB}$ |
题解
思路
考虑一个数 $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;
}
近期评论