codeforces 766-div2 D

题目 题意: 给定n个数的数组，若数组中任意两个数的gcd没有在数组中出现，则将其加入数组，直至数组稳定。求至多可以加入多少个数. 思路: 不会。。。 看了大佬的视频，说是套路题，观察n =1e6。又是数论的题，不是二分就是调和级数。 二分不太现实，调和级数的时间复杂度也就是埃氏筛。 用类似埃氏筛的方法对范围内每个数从大到小进行筛选，枚举其所有倍数，求所有其倍数在数组中可能出现的数的公共gcd.以此来判断该数能否出现。 如果从小到大筛的话不一定保证其倍数是否判断过能否出现，会有误。 时间复杂度: O(nloglogn) 代码:

// Problem: D. Not Adding
// Contest: Codeforces - Codeforces Round #766 (Div. 2)
// URL: https://codeforces.com/contest/1627/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;i=1;--i)
	{
		int tmp = 0; //所有在数组中可能出现的i的倍数的gcd
		for(int j=2;i*jT;
   // read(T);
   while(T--)
   {
   	 solve();
   }
   return 0;
}