D. Mahmoud and Ehab and another array construction task(贪心,质因子)

数论的题一窍不通

虽然这题这题只能算半个数论题

先

来

一

遍

欧

拉

筛

,

顺

便

记

录

z

h

i

[

x

]

表

示

的

最

小

质

因

子

先来一遍欧拉筛,顺便记录zhi[x]表示x的最小质因子

先来一遍欧拉筛,顺便记录zhi[x]表示x的最小质因子

利

用

数

组

可

以

快

速

分

解

利用zhi[x]数组可以快速分解质因子

利用zhi[x]数组可以快速分解质因子

对

于

已

经

选

择

标

所

有

后

续

不

能

这

个

了

对于已经选择的数,标记所有质因子,表示后续不能选这个质因子了

对于已经选择的数,标记所有质因子,表示后续不能选这个质因子了

Ⅰ

.

当

前

字

典

序

还

未

分

胜

负

\color{Red}Ⅰ.当前字典序还未分胜负

Ⅰ.当前字典序还未分胜负

那

就

从

a

i

开

始

暴

力

判

断

是

否

和

前

面

冲

突

那就从a_i这个数开始,暴力的一个一个判断是否和前面冲突

那就从ai​这个数开始,暴力的一个一个判断是否和前面冲突

旦

发

现

马

上

并

一旦发现不冲突就马上选,并对选择的数分解质因子标记

一旦发现不冲突就马上选,并对选择的数分解质因子标记

Ⅱ

已

\color{Red}Ⅱ.字典序已分胜负

Ⅱ.字典序已分胜负

#include <bits/stdc++.h>
using namespace std;
const int inf=3e6+10;
const int maxn=1e5+10;
int flag,a[maxn],b[maxn];
int prime[inf+10],zhi[inf+10],n,top,use[inf+10];
bool vis[inf+10];
void make_prime()
{
	for(int i=2;i<=inf;i++)
	{
		if( !vis[i] )	prime[++top]=i,zhi[i]=i;
		for(int j=1;j<=top&&i*prime[j]<=inf;j++ )
		{
			vis[ i*prime[j] ]=1;
			zhi[ i*prime[j] ]=prime[j];
			if( i%prime[j]==0 )	break;
		}
	}
}
bool check( int x )
{
	while( x>=2 )
	{
		if( use[ zhi[x] ] )	return false;
		x/=zhi[x];
	}
	return true;
}
int main()
{
	make_prime();
	cin >> n;
	for(int i=1;i<=n;i++)	cin >> a[i];
	int j=1;
	for(int i=1;i<=n;i++)
	{
		if( flag )//已分胜负,那么选最小的质数 
		{
			while( use[ prime[j]] )	j++;
			use[ prime[j] ]=1;
			b[i]=prime[j];
		} 
		else//未分胜负,暴力找大于a[i]且和前面不冲突的数 
		{
			int k=a[i];
			while( !check(k) )	k++;
			if( k>a[i] )	flag=1;
			b[i]=k;
			while( k>=2 )//标记k的所有质因子 
			{
				use[ zhi[k] ]=1;
				k/=zhi[k];//分解素数 
			}
		}
	}
	for(int i=1;i<=n;i++)	cout << b[i] << " ";
}