当前位置：首页 > news >正文

hdu4407 n(n=400000)个数，a[i]=i，m个询问及更改(m=1000)，更改某个位置的数，询问区间与这个数互质数的和：容斥/离线...

news 来源：原创 2024/5/10 3:21:59

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

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

 1 #include<stdio.h>
 2 #include<math.h>
 3 #include<string.h>
 4 #include<algorithm>
 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].q&&b[i].l>=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 }