D. Mahmoud and Ehab and another array construction task 因子分解模板

题意

给出一个原序列a 找出一个字典序大于a的序列b，使得任意 \(i!=j\),\(gcd(a[i],a[j])==1\)，现在要你找出这样的序列b,并且满足所有合法序列中输出字典序最小的那个

思路

维护一个set,set里面装所有当前可以取的合法元素，先把所有的数字放进set里面，因为要求字典序最小的序列b，并且b的字典序要大于a，当构造的b到当前位置截止时和a相同时，每次在set里面二分找第一个大于等于当前位置a的值，当不相同时，直接每次取set的最小的元素也就是首元素以满足构造的b字典序最小

因子分界模板（听说是nlog(n),有空证一下）

void init(){

	for(int i=2;i<maxn;i++){

		if(!vis[i]){

			vis[i]=1;

			for(int j=i;j<maxn;j+=i){

				vis[j]=1;

				v[j].pb(i);

			}

		}

	}

}

AC代码

#include<bits/stdc++.h>

#define pb push_back

#define F first

#define S second

#define pii pair<int,int>

using namespace std;

const int maxn=2e6+200;

bool vis[maxn+5];

set<int>s;

vector<int>v[maxn];

void init(){

	for(int i=2;i<maxn;i++){

		if(!vis[i]){

			vis[i]=1;

			for(int j=i;j<maxn;j+=i){

				vis[j]=1;

				v[j].pb(i);

			}

		}

		s.insert(i);

	}

}

bool vis2[maxn];

int main(){

	int n;

	init();

	scanf("%d",&n);

	int tmp;

	int flag=1;

	for(int i=1;i<=n;i++){

		scanf("%d",&tmp);

		int now=*s.begin();

		if(flag){

			now=*s.lower_bound(tmp);

			if(now!=tmp)flag=0;

		}

		//s.erase(now);

		printf("%d ",now);

		for(int &x:v[now]){

			for(int j=x;j<maxn;j+=x){

				if(!vis2[j]){

					vis2[j]=1;

					s.erase(j);

				}

			}

		}

	}

//	for(int i=1;i<=n;i++)printf("%d ",ans[i]);

	return 0;

}

巴特西

D. Mahmoud and Ehab and another array construction task 因子分界模板+贪心+数学

D. Mahmoud and Ehab and another array construction task 因子分解模板

题意

思路

因子分界模板（听说是nlog(n),有空证一下）

AC代码

最新文章

热门文章

巴特西

D. Mahmoud and Ehab and another array construction task 因子分界模板+贪心+数学

D. Mahmoud and Ehab and another array construction task 因子分解模板

题意

思路

因子分界模板 （听说是nlog(n),有空证一下）

AC代码

最新文章

热门文章

因子分界模板（听说是nlog(n),有空证一下）