題目大意
定義一個(gè)集合A昼榛，如果x和y屬于A，那么x和y的最大公約數(shù)也屬于A剔难。問題給出n個(gè)屬于集合A的數(shù)字胆屿，問集合A最少有多少個(gè)不同的數(shù)字奥喻。n<=105，集合A的數(shù)字均<=106莺掠。
解答
我的做法是衫嵌，開一個(gè)10^6（下記為M）的數(shù)組記錄集合A是否包含某個(gè)元素。從大到小枚舉彻秆，判斷一個(gè)最初不在集合A的數(shù)字i是否也屬于集合A楔绞。判斷的方式是找出所有在集合A的i的倍數(shù)，選兩個(gè)數(shù)唇兑，看這兩個(gè)數(shù)的gcd是否為i酒朵。找出所有i的倍數(shù)的時(shí)間復(fù)雜度是O(M*log(M))的，不會(huì)超時(shí)扎附。但是判斷是否存在兩個(gè)數(shù)的gcd為i我能想到的做法就是容斥蔫耽。設(shè)i×j[1],i×j[2]...i×j[m]是i的屬于集合A的倍數(shù)，把j[1],j[2],...,j[m]質(zhì)因數(shù)分解留夜，枚舉j[k] (1<=k<=m)匙铡，用容斥原理算出與j[k]不互質(zhì)的個(gè)數(shù)t，只要t<m碍粥，那么i的倍數(shù)中就存在兩個(gè)數(shù)的gcd是i鳖眼，i就是在集合A的數(shù)字。
質(zhì)因數(shù)分解需要先預(yù)處理好嚼摩，容斥的時(shí)候钦讳，我害怕超時(shí)，盡量用上重復(fù)的信息(比如判斷i1和i2的時(shí)候枕面，它們都有相同倍數(shù)在同一集合愿卒，可以重復(fù)利用)。
這個(gè)做法理論上時(shí)間復(fù)雜度很大潮秘，每次容斥都是O(2^質(zhì)數(shù)個(gè)數(shù))琼开，但是由于實(shí)際上質(zhì)數(shù)的個(gè)數(shù)跟容斥的數(shù)有關(guān)，所以大部分情況下不是很大枕荞，再加上只是需要判斷存在與否柜候，所以實(shí)際跑起來不會(huì)很慢，在比賽的時(shí)候過掉了所有的test买猖。
比賽的時(shí)候改橘，由于太久沒寫容斥了，寫add和que函數(shù)的時(shí)候都算了正負(fù)號(hào)玉控，計(jì)算的結(jié)果相當(dāng)于全部加了起來飞主。
xb由于不太滿意我的做法，后來想到了一個(gè)正確的做法，時(shí)間復(fù)雜度就是O(M*log(M))碌识。
這個(gè)集合有個(gè)關(guān)鍵性質(zhì)碾篡，給出的n個(gè)數(shù)的非空子集的gcd一定在集合內(nèi)，并且不屬于給出n個(gè)數(shù)的數(shù)字一定是這n個(gè)數(shù)中的一個(gè)子集的gcd筏餐。我們可以用逆推的方法得到這個(gè)結(jié)論开泽。設(shè)給出n個(gè)數(shù)的集合為S，集合A為最終答案魁瞪。若x∈A穆律，x=gcd(a,b)，a∈S而b?S导俘。那么可以讓b=gcd(c,d)這樣迭代替換下去峦耘，直到全部元素屬于S為止。
在上面性質(zhì)的前提下旅薄，xb有一個(gè)很強(qiáng)大的判斷辅髓，決定當(dāng)i?S時(shí)，是否屬于A少梁。
設(shè)cnt[i]表示S集合中i的倍數(shù)的個(gè)數(shù)洛口。如果y是x的倍數(shù)，那么顯然有cnt[x]>=cnt[y]凯沪，當(dāng)cnt[x]=cnt[y]時(shí)第焰，意味著x和y在S中的倍數(shù)是完全一樣的，由于y是x的倍數(shù)著洼，所以不可能在x和y的倍數(shù)中找到一個(gè)子集gcd是x樟遣，所以x?A而叼。
反過來身笤，如果x的所有倍數(shù)y，都有cnt[x]>cnt[y]葵陵，那么一定有x∈A液荸。這時(shí)求x的所有倍數(shù)的gcd，一定是x脱篙。
這個(gè)做法十分的強(qiáng)大娇钱，具體可以參看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;
}
