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] << " ";
}