注意到m的范围很小，允许m2，然后重要的起始条件a[i]=i，这样可以k=1的时候用容斥预处理算出答案，然后离线保存

在k=2的时候暴力m2更改答案

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #define LL long long 6 using namespace std; 7 struct A{ 8   LL l,r,p,q,ans; 9 }a[1005];10 struct B{11   LL l,p,q;12 }b[1005];13 LL ans,tmp,ql,qr,cnt=0,prime[400005],vis[400005],f[15],x[400005];14 LL gcd(LL a1,LL a2)15 {16   if (a2==0) return a1;17   return gcd(a2,a1%a2);18 }19 LL sum(LL b,LL l)20 {21   l=l/b*b;22   return (b+l)*((l-b)/b+1)/2;23 }24 void dfs(LL now,LL flag,LL bei)25 {26   if (flag) ans+=sum(bei,qr)-sum(bei,ql-1);27   else ans-=sum(bei,qr)-sum(bei,ql-1);28   for (LL i=now+1;i<=tmp;i++)29     dfs(i,1-flag,bei*f[i]);30 }31 LL cal(LL l,LL r,LL p)32 {33   LL sqr,i;34   tmp=0; sqr=(LL)sqrt(1.0*p);35   for (i=1;i<=cnt&&prime[i]<=sqr;i++)36     if (p%prime[i]==0){37       f[++tmp]=prime[i];38       while (p%prime[i]==0) p/=prime[i];39     }40   if (p!=1) f[++tmp]=p;41   ans=0; ql=l; qr=r;42   for (i=1;i<=tmp;i++)43     dfs(i,1,f[i]);44   return (l+r)*(r-l+1)/2-ans;45 }46 int main()47 {48   LL i,j,T,n,m,c1,c2,k;49   memset(vis,0,sizeof(vis));50   for (i=2;i<=400000;i++)51     if (vis[i]==0)52     {53       prime[++cnt]=i;54       for (j=2;i*j<=400000;j++) vis[i*j]=1;55     }56   scanf("%I64d",&T); 57   while (T--){58     scanf("%I64d%I64d",&n,&m);59     c1=c2=0;60     for (i=1;i<=m;i++){61       scanf("%I64d",&k);62       if (k==1){63         c1++;64         scanf("%I64d%I64d%I64d",&a[c1].l,&a[c1].r,&a[c1].p);65         a[c1].q=i; a[c1].ans=cal(a[c1].l,a[c1].r,a[c1].p);66       }67       else{68         c2++;69         scanf("%I64d%I64d",&b[c2].l,&b[c2].p);70         b[c2].q=i;71       }72     }73     for (i=1;i<=n;i++) x[i]=i;74     for (i=1;i<=c2;i++){75       for (j=1;j<=c1;j++)76         if (b[i].q
          
           =a[j].l&&b[i].l<=a[j].r){77           if (gcd(x[b[i].l],a[j].p)==1) a[j].ans-=x[b[i].l];78           if (gcd(b[i].p,a[j].p)==1) a[j].ans+=b[i].p;79         }80       x[b[i].l]=b[i].p;81     }82     for (i=1;i<=c1;i++) printf("%I64d\n",a[i].ans);83   }84 }
          
         
        
       
      

题目链接：