[cf] 766 div2 D. Not Adding

前言

t a g : tag : tag: gcd 数学 值域 *1900 传送门 :

题意 : 给定一个数组 a [ ] a[] a[],询问可以执行多少次操作

操作定义如下 : 选择 i , j i,j i,j,如果 g c d ( i , j ) gcd(i,j) gcd(i,j)不在数组 a [ ] a[] a[]将其加入数组末尾

思路 :

因为 g c d gcd gcd只会使得值越来越小

所以我们可以得知答案的区间在 [ 1 , m a x ( a [ 1... n ] ) ] [1,max(a[1...n])] [1,max(a[1...n])]

因为范围 1 e 6 1e6 1e6,因此我们可以暴力的枚举每个答案

我们考虑类似筛法的思想,枚举每个 x x x的倍数 y y y

如果 y y y在数组中,我们就对其作一次 g c d gcd gcd,因为我们每次枚举的都是 x x x的倍数,所以如果最后答案是 x x x的话,我们就对答案计算一次贡献

最后再减去数组本身就存在的即可

code :

int mp[N];

int n;
int a[N];
void solve(){
	cin>>n;
	int maxn = - INF;
	
	for(int i=1;i>a[i];
		mp[a[i]] = 1;
		
		maxn = max(a[i],maxn);
	}
	
	
	
	int res = 0 ;
	for(int i=1;i