【题解】[牛客网NOIP赛前集训营-提高组（第七场）]B.随机生成树 枚举

题目链接

#include<cstdio>
const int N=5e5+10;
inline int read()
{
	int s=0,f=0;char ch=getchar();
	while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
	if(f)s=-s;return s;
}
int n,c[N],vis[N],ans=1;
int main()
{
	//freopen("in.txt","r",stdin);
    n=read();
    for(int i=1;i<=n;i++)
        c[i]=read();
    for(int i=1;i<=n;i++)
        for(int j=i*2;j<=n;j+=i)
            if(c[i]!=c[j]&&!vis[j])
                vis[j]=1,ans++;
    printf("%d\n",ans);
    return 0;
}

总结

这波模型转换很精髓