51nod lyk与gcd

基准时间限制：2 秒空间限制：131072 KB 分值: 80 难度：5级算法题

这天，lyk又和gcd杠上了。
它拥有一个n个数的数列，它想实现两种操作。

1：将 ai 改为b。
2：给定一个数i，求所有 gcd(i,j)=1 时的 aj 的总和。

Input

第一行两个数n，Q(1<=n,Q<=100000)。

接下来一行n个数表示ai(1<=ai<=10^4)。

接下来Q行，每行先读入一个数A(1<=A<=2)。

若A=1，表示第一种操作，紧接着两个数i和b。(1<=i<=n,1<=b<=10^4)。

若B=2，表示第二种操作，紧接着一个数i。(1<=i<=n)。

Output

对于每个询问输出一行表示答案。

Input示例

Output示例

9

7
思路 

考虑辅助数组f[i]表示所有下标为i的倍数的a数组的总和。

例如有5个数，那么f[1]=a[1]+a[2]+a[3]+a[4]+a[5]，f[2]=a[2]+a[4]，f[3]=a[3]，f[4]=a[4]，f[5]=a[5]。

对于每一个修改操作，我们只需要求出i的所有因数，然后将下标为它的因数的f数组中修改值即可。

对于所有询问操作，求出i的所有因数p1,p2,p3...之后答案即为Σu[pi]*f[pi]。

其中u为mobius函数。

总复杂度为所有操作中i的因数个数总和。

利用容斥定理----

先将每个数加到它的约数里---

然后每次利用容斥定理求出和 i 不互素的数的和---

总和-求的和就为所要的解

#include<cstdio>

#include<cmath>

#include<vector>

#include<cstring>

#include<algorithm>

using namespace std;

#define LL long long

vector <int > sta[];

int shu[];

int ou[],ll;

int qu[],kkp;

LL pp[];

void init(int n)

{

    int su[],kp=;

    bool fa[];

    memset(fa,true,sizeof(fa));

    for (int i=;i<=n;i++)

    {

        if (fa[i])

        {

            su[kp++]=i;

            if (i<=sqrt(n))

            for (int j=i*i;j<=n;j+=i)

                fa[j]=false;

        }

    }

    for (int i=;i<=n;i++)

    {

        int ll=;

        int kk=i;

        for (int j=;su[j]*su[j]<=kk;j++)

        {

            if (kk%su[j]==)

                ou[ll++]=su[j];

            while (kk%su[j]==)

                kk/=su[j];

        }

        if (kk>)

            ou[ll++]=kk;

        kkp=;

        qu[kkp++]=-;

        for (int j=;j<ll;j++)

        {

            kk=kkp;

            for (int k=;k<kk;k++)

                qu[kkp++]=qu[k]*ou[j]*-;

        }

        for (int j=;j<kkp;j++)

            sta[i].push_back(qu[j]);

    }

}

int main()

{

    int n,k;

    /*freopen("In.txt","r",stdin);

    freopen("wo.txt","w",stdout);*/

    scanf("%d%d",&n,&k);

    init(n);

    LL s=,ans;

    memset(pp,,sizeof(pp));

    for (int i=;i<=n;i++)

    {

        scanf("%d",&shu[i]);

        for (int j=;j<sta[i].size();j++)

        {

            if (sta[i][j]>)

                pp[sta[i][j]]+=shu[i];

            else

                pp[-sta[i][j]]+=shu[i];

        }

        s+=shu[i];

    }

    int a,b,c;

    while (k--)

    {

        scanf("%d",&c);

        if (c==)

        {

            scanf("%d%d",&a,&b);

            for (int j=;j<sta[a].size();j++)

            {

                if (sta[a][j]>)

                    pp[sta[a][j]]-=shu[a];

                else

                    pp[-sta[a][j]]-=shu[a];

            }

            s-=shu[a];

            shu[a]=b;

            for (int j=;j<sta[a].size();j++)

            {

                if (sta[a][j]>)

                    pp[sta[a][j]]+=shu[a];

                else

                    pp[-sta[a][j]]+=shu[a];

            }

            s+=shu[a];

        }

        else

        {

            scanf("%d",&a);

            if (a==)

            {

                printf("%lld\n",s);

                continue;

            }

            ans=;

            for (int i=;i<sta[a].size();i++)

            {

                if (sta[a][i]<)

                    ans-=pp[-sta[a][i]];

                else

                    ans+=pp[sta[a][i]];

            }

            ans=s-ans;

            printf("%lld\n",ans);

        }

    }

    return ;

}

这道题是我复制借鉴的http://blog.csdn.net/leibniz_zhang/article/details/52318715这位大佬的 = =

巴特西

51nod lyk与gcd

最新文章

热门文章