HDU-4407-Sum(容斥原理)「建议收藏」

对于每一次询问。先不考虑数字被改动了。那我们能够直接用求和公式把x到y之间的数字的和求出来，然后再减去那些不和p互质的数(用容斥原理)，再对改动过的数进行特判就可以。

#include <stdio.h>

int num,idx[1005],val[1005],prime[10],p[40000];

inline bool check(int x)
{
    int i;

    for(i=0;i<num;i++) if(x%prime[i]==0) return 0;

    return 1;
}

int main()
{
    int T,n,m,i,j,k,type,cnt,a,b,c,last,lxdcnt,lxdnum,l,r;
    long long ans;

    //把40W以内的素数预处理出来-----------------
    cnt=0;

    for(i=2;i<400000;i++)
    {
        for(j=2;j*j<=i;j++) if(i%j==0) break;

        if(j*j>i) p[cnt++]=i;
    }
    //------------------------------------------

    scanf("%d",&T);

    while(T--)
    {
        scanf("%d%d",&n,&m);

        cnt=0;

        for(i=1;i<=m;i++)
        {
            scanf("%d",&type);

            if(type==1)
            {
                scanf("%d%d%d",&a,&b,&c);

                ans=(long long)(a+b)*(b-a+1)/2;

                num=0;//质因数的个数

                //获取c的质因数-----------------
                last=0;

                while(c>1)
                {
                    if(c%p[last]==0)
                    {
                        prime[num++]=p[last];
                        c/=p[last];
                        while(c%p[last]==0) c/=p[last];
                    }

                    last++;
                }
                //-------------------------------

                //容斥原理-------------------------
                for(j=1;j<(1<<num);j++)
                {
                    lxdcnt=0;
                    lxdnum=1;

                    for(k=0;k<num;k++) if(j&(1<<k))
                    {
                        lxdcnt++;
                        lxdnum*=prime[k];
                    }


                    l=a/lxdnum*lxdnum;
                    if(l<a) l+=lxdnum;
                    r=b/lxdnum*lxdnum;
                    if(r<l) continue;

                    if(lxdcnt&1) ans-=(long long)(l+r)*((r-l)/lxdnum+1)/2;
                    else ans+=(long long)(l+r)*((r-l)/lxdnum+1)/2;
                }
                //-----------------------------------

                //对改动过的数字特殊推断-----------------------------------
                for(j=0;j<cnt;j++)
                {
                    if(idx[j]>=a && idx[j]<=b)
                    {
                        if(!check(idx[j]))
                        {
                            if(check(val[j])) ans+=val[j];
                        }
                        else
                        {
                            if(check(val[j])) ans=ans+val[j]-idx[j];
                            else ans-=idx[j];
                        }
                    }
                }
                //--------------------------------------------------------

                printf("%I64d\n",ans);
            }
            else
            {
                scanf("%d%d",&a,&b);

                for(j=0;j<cnt;j++) if(idx[j]==a)//注意，改动的点可能之前已被改动过
                {
                    val[j]=b;
                    break;
                }

                if(j==cnt)
                {
                    idx[cnt]=a;
                    val[cnt++]=b;
                }
            }
        }
    }
}