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

数论的题一窍不通

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

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

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

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

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

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

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

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