题目大意
定义一个集合A，如果x和y属于A，那么x和y的最大公约数也属于A。问题给出n个属于集合A的数字，问集合A最少有多少个不同的数字。n<=105，集合A的数字均<=106。
解答
我的做法是，开一个10^6（下记为M）的数组记录集合A是否包含某个元素。从大到小枚举，判断一个最初不在集合A的数字i是否也属于集合A。判断的方式是找出所有在集合A的i的倍数，选两个数，看这两个数的gcd是否为i。找出所有i的倍数的时间复杂度是O(M*log(M))的，不会超时。但是判断是否存在两个数的gcd为i我能想到的做法就是容斥。设i×j[1],i×j[2]...i×j[m]是i的属于集合A的倍数，把j[1],j[2],...,j[m]质因数分解，枚举j[k] (1<=k<=m)，用容斥原理算出与j[k]不互质的个数t，只要t<m，那么i的倍数中就存在两个数的gcd是i，i就是在集合A的数字。
质因数分解需要先预处理好，容斥的时候，我害怕超时，尽量用上重复的信息(比如判断i1和i2的时候，它们都有相同倍数在同一集合，可以重复利用)。
这个做法理论上时间复杂度很大，每次容斥都是O(2^质数个数)，但是由于实际上质数的个数跟容斥的数有关，所以大部分情况下不是很大，再加上只是需要判断存在与否，所以实际跑起来不会很慢，在比赛的时候过掉了所有的test。
比赛的时候，由于太久没写容斥了，写add和que函数的时候都算了正负号，计算的结果相当于全部加了起来。
xb由于不太满意我的做法，后来想到了一个正确的做法，时间复杂度就是O(M*log(M))。
这个集合有个关键性质，给出的n个数的非空子集的gcd一定在集合内，并且不属于给出n个数的数字一定是这n个数中的一个子集的gcd。我们可以用逆推的方法得到这个结论。设给出n个数的集合为S，集合A为最终答案。若x∈A，x=gcd(a,b)，a∈S而b∉S。那么可以让b=gcd(c,d)这样迭代替换下去，直到全部元素属于S为止。
在上面性质的前提下，xb有一个很强大的判断，决定当i∉S时，是否属于A。
设cnt[i]表示S集合中i的倍数的个数。如果y是x的倍数，那么显然有cnt[x]>=cnt[y]，当cnt[x]=cnt[y]时，意味着x和y在S中的倍数是完全一样的，由于y是x的倍数，所以不可能在x和y的倍数中找到一个子集gcd是x，所以x∉A。
反过来，如果x的所有倍数y，都有cnt[x]>cnt[y]，那么一定有x∈A。这时求x的所有倍数的gcd，一定是x。
这个做法十分的强大，具体可以参看xb的题解
以下是我容斥暴力的代码
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define bll long long
#define For(i,a,b) for (int i=(a),_##i=(b); i<=_##i; i++)
#define Rof(i,a,b) for (int i=(a),_##i=(b); i>=_##i; i--)
#define Mem(a,b) memset(a,b,sizeof(a))
const int maxL=1000*1000+10;
int N,fp[maxL],Prime[maxL],M;
int nex[maxL],G[maxL];
bool boo[maxL];
void Preapre()
{
Mem(fp,0);
Prime[0]=0;
For(i,2,maxL-1)
{
if (!fp[i]) fp[i]=i,Prime[++Prime[0]]=i;
For(j,1,Prime[0])
{
if (i*Prime[j]>=maxL) break;
fp[i*Prime[j]]=Prime[j];
if (i%Prime[j]==0) break;
}
}
nex[1]=1;
For(i,2,maxL-1)
{
int x=i;
int p=fp[i];
while(x%p==0) x/=p;
nex[i]=x;
}
}
int gcd(int a,int b)
{
if (b==0) return a;
return gcd(b,a%b);
}
void add(int state,int x,int d)
{
if (x==1)
{
if (state>1) G[state]+=d;
return ;
}
add(state*fp[x],nex[x],-d);
add(state,nex[x],d);
}
int que(int state,int x)
{
if (x==1)
{
return G[state];
}
int ret=0;
ret+=que(state*fp[x],nex[x]);
ret+=que(state,nex[x]);
return ret;
}
void Done()
{
static bool vis[maxL];
static int o[maxL];
Mem(vis,0);
Mem(G,0);
Rof(i,M,1)
if (!boo[i])
{
int rr=0;
for (int j=2; j*i<=M; j++)
{
bool flag=boo[j*i];
if (flag) o[++rr]=j;
if (flag!=vis[j])
{
add(1,j,(flag ? -1 : 1));
vis[j]=flag;
}
}
For(j,1,rr)
{
int ret=que(1,o[j]);
if (ret<rr)
{
boo[i]=1;
break;
}
}
}
int ans=0;
For(i,1,M)
ans+=boo[i];
printf("%d\n",ans);
}
int main(int argc, char* argv[])
{
Preapre();
for (; scanf("%d",&N)!=EOF; )
{
Mem(boo,0);
M=0;
For(i,1,N)
{
int x; scanf("%d",&x);
M=max(M,x);
boo[x]=1;
}
Done();
}
return 0;
}
