CF1034A Enlarge GCD

emmm真是简短的题意,真是妙题一个 假设原数组的 g c d gcd gcd为 g g g 考虑唯一分解的形式: g c d = ∏ p i m i n ( c 1 , c 2 , c 3.... c i ) gcd=\prod p_i^{min(c1,c2,c3....c_i)} gcd=∏pimin(c1,c2,c3....ci​)​ 先把 每个 a i / g 每个ai/g 每个ai/g, 现在 g = g c d ( a 1.... a n ) = 1 , 我们需要把 g 变得更大 g=gcd(a1....an)=1,我们需要把g变得更大 g=gcd(a1....an)=1,我们需要把g变得更大 假设变成了 g 1 g1 g1,可以说, g 1 g1 g1是个素数的情况一定更优,如果 g 1 g1 g1是一个合数,那么 a i a_i ai​中包含它的因子也必定包含 g 1 / d g1/d g1/d的形式,所以 g 1 g1 g1是素数的情况一定不会更差 而素数的个数有 n / l o g n n/logn n/logn个. 如果我们之前枚举 1.5 ∗ 1 0 7 ∗ l o g ( 1.5 ∗ 1 0 7 ) = 1.5 ∗ 1 0 7 ∗ 23 1.5*10^7*log(1.5*10^7)=1.5*10^7*23 1.5∗107∗log(1.5∗107)=1.5∗107∗23 这个复杂度是一定会超时的,如果改为 1.5 ∗ 1 0 7 / 23 = 1 0 6 1.5*10^7/23=10^6 1.5∗107/23=106.这个数量级情况下可以通过 O ( n l o g n ) O(nlogn) O(nlogn)的筛法.

/*
You held me down but I broke free,
I found the love inside of me.
Now I don't need a hero to survive
Cause I already saved my life.
*/
#include
using namespace std;
const int maxn = 1.5e7+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
int in[maxn];
const int maxm = 3e5+2;
int a[maxm];
//筛子
vector pr;bool vis[maxn];
void table(int n){
	for(int i=2;in) break;
			vis[i*p] = true;
			if(i%p==0) break;
		}
	}
}
int gcd(int a,int b){
	if(!b)return a;
	return gcd(b,a%b);
}
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int MX = 0;int n;
	cin>>n;int g = 0;
	for(int i=1;i>a[i];g = gcd(a[i],g);
	}
	for(int i=1;i