51nod 1616 最小集合( 数论 )

题目链接

题目大意

定义一个集合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;
}

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 14,349评论 0 33
  • thiele插值算法 1点插值算法 function [C,c]=thiele(X,Y,Z)%X为插值点横坐标,Y...
    00crazy00阅读 6,240评论 0 4
  • SwiftDay011.MySwiftimport UIKitprintln("Hello Swift!")var...
    smile丽语阅读 9,242评论 0 6
  • 你说月洒寒江,玉柱琼梁; 后来冷镜残钩,三更榻凉。 你说梦呓故园 ,桃花水里游鸳鸯; 后来千山暮雪,老翅 几回自奔...
    巧克力吐司阅读 1,800评论 0 0
  • 启动页是一个应用的入口,所以在该软件进入主界面之前应该需要做些什么工作,是要很清楚的。 启动页的功能: 1:延时跳...
    隰有荷阅读 1,638评论 0 2