51nod oj 1678 lyk與gcd 【容斥定理+打表】

傳送門：​​1678​​

​​1678 lyk與gcd​​

基準時間限制：2 秒 空間限制：131072 KB 分值: 80 

​​難度：5級算法題​​

 收藏

 關注

這天，lyk又和gcd杠上了。

它擁有一個n個數的數列，它想實作兩種操作。

1：将  

 改為b。

2：給定一個數i，求所有 

 時的  

  的總和。

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示例

5 31 2 3 4 52 41 3 12 4

Output示例

97

利用容斥定理-----

先将每個數加到它的約數裡----

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

總和-求的和就為所要的解

#include<cstdio>
#include<cmath> 
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
vector <int > sta[200100];
int shu[220000];
int ou[100],ll;
int qu[200100],kkp;
LL pp[200100];
void init(int n)
{
  int su[200100],kp=0;
  bool fa[200100];
  memset(fa,true,sizeof(fa));
  for (int i=2;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=2;i<=n;i++)
  {
    int ll=0;
    int kk=i;
    for (int j=0;su[j]*su[j]<=kk;j++)
    {
      if (kk%su[j]==0)
        ou[ll++]=su[j];
      while (kk%su[j]==0)
        kk/=su[j];
    }
    if (kk>1)
      ou[ll++]=kk;
    kkp=0;
    qu[kkp++]=-1;
    for (int j=0;j<ll;j++)
    {
      kk=kkp;
      for (int k=0;k<kk;k++)
        qu[kkp++]=qu[k]*ou[j]*-1;
    }
    for (int j=1;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=0,ans;
  memset(pp,0,sizeof(pp));
  for (int i=1;i<=n;i++)
  {
    scanf("%d",&shu[i]);
    for (int j=0;j<sta[i].size();j++)
    {
      if (sta[i][j]>0)
        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==1)
    {
      scanf("%d%d",&a,&b);
      for (int j=0;j<sta[a].size();j++)
      {
        if (sta[a][j]>0)
          pp[sta[a][j]]-=shu[a];
        else
          pp[-sta[a][j]]-=shu[a];
      }
      s-=shu[a];
      shu[a]=b;
      for (int j=0;j<sta[a].size();j++)
      {
        if (sta[a][j]>0)
          pp[sta[a][j]]+=shu[a];
        else
          pp[-sta[a][j]]+=shu[a];
      }
      s+=shu[a];
    }
    else
    {
      scanf("%d",&a);
      if (a==1)
      {
        printf("%lld\n",s);
        continue;
      }
      ans=0;
      for (int i=0;i<sta[a].size();i++)
      {
        if (sta[a][i]<0)
          ans-=pp[-sta[a][i]];
        else
          ans+=pp[sta[a][i]];
      } 
      ans=s-ans;
      printf("%lld\n",ans);
    }
  }
  return 0;
}