【BZOJ 3529】 [Sdoi2014]数表 （莫比乌斯+分块+离线+树状数组）

时间：2023-03-22 18:50:08

3529: [Sdoi2014]数表

Description

有一张N×m的数表，其第i行第j列（1 < =i < =礼，1 < =j < =m）的数值为
能同时整除i和j的所有自然数之和。给定a，计算数表中不大于a的数之和。

Input

输入包含多组数据。
    输入的第一行一个整数Q表示测试点内的数据组数，接下来Q行，每行三个整数n，m，a(|a| < =10^9)描述一组数据。

Output

对每组数据，输出一行一个整数，表示答案模2^31的值。

Sample Input

2
4 4 3
10 10 5

Sample Output

20
148
【分析】
　　先假设没有a的限制。。
　　设g(i)=ΣΣ[(x,y)==i](1<=x<=n,1<==y<=m)
　　   g(i)=Σmu[d]*(n/(i*d))*(m/(i*d))
     尝试把i和d分开，设D=i*d
　　那么g(i)=(n/D)*(M/D)*Σmu[i/D]  (i|D)
　　设f(i)为i的约数和，这个可以nlogn求出来，那么ans=g(i)*f(i)=(n/D)*(M/D)*Σmu[i/D]*f(i) (i|D)
　　对于a的限制，是说f(i)<=a的东西对ans有贡献，其他的没有贡献。
　　所以就离线一下~~按照f(i)排序，询问按照a排序，因为要询问前缀和，所以当他开始有贡献的时候就把他放到树状数组里面去。
　　剩下的就是分块处理了。
　　Mod的地要自然溢出最后取模？不然会超时，像我一样~
 
　　别人的题解：
【BZOJ 3529】 [Sdoi2014]数表 （莫比乌斯+分块+离线+树状数组）
代码如下：
 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<queue>

 #include<cmath>

 using namespace std;

 #define Maxn 100010

 #define LL unsigned int

 #define INF 0xfffffff

 LL mx;

 LL Mod;

 int mu[Maxn];

 LL pri[Maxn],pl;

 bool q[Maxn];

 struct node

 {

     LL x,y,a,ans,id;

 }t[Maxn],f[Maxn];

 LL mymin(LL x,LL y) {return x<y?x:y;}

 LL mymax(LL x,LL y) {return x>y?x:y;}

 bool cmp(node x,node y) {return x.a<y.a;}

 bool cmp2(node x,node y) {return x.id<y.id;}

 void get_mu()

 {

     pl=;

     memset(q,,sizeof(q));

     mu[]=;

     for(LL i=;i<=mx;i++)

     {

         if(q[i])

         {

             pri[++pl]=i;

             mu[i]=-;

         }

         for(LL j=;j<=pl;j++)

         {

             if(i*pri[j]>mx) break;

             q[i*pri[j]]=;

             if(i%pri[j]==) mu[i*pri[j]]=;

             else mu[i*pri[j]]=-mu[i];

             if(i%pri[j]==) break;

         }

     }

     for(LL i=;i<=mx;i++) f[i].a=;

     for(LL i=;i<=mx;i++)

      for(LL j=i;j<=mx;j+=i)

         f[j].a=f[j].a+i;

     for(LL i=;i<=mx;i++) f[i].id=i;

 }

 LL c[Maxn],as[Maxn];

 LL add(LL x,LL y)

 {

     as[x]+=y;

     for(LL i=x;i<=mx;i+=i&(-i))

         c[i]+=y;

 }

 LL get_sum(LL x)

 {

     LL ans=;

     for(LL i=x;i>=;i-=i&(-i))

       ans+=c[i];

     return ans;

 }

 void change(LL x)

 {

     LL now=f[x].id;

     for(LL i=now;i<=mx;i+=now)

       add(i,(LL)(mu[i/now]*f[x].a));

 }

 LL get_ans(LL n,LL m)

 {

     LL ans=,t;

     if(n>m) t=n,n=m,m=t;

     LL sq=(LL)ceil(sqrt((double)m));

     for(LL i=;i<=mymin(sq,n);i++)

     {

         LL x=(LL)(n/i),y=(LL)(m/i);

         ans+=as[i]*(n/i)*(m/i);

     }

     for(LL i=sq+;i<=n;)

     {

         LL x=n/i,y=m/i;

         LL r1=n/x+,r2=m/y+;

         if(r1>n+) r1=n+;

         if(r2>n+) r2=n+;

         LL r=mymin(r1,r2);

         ans+=(get_sum(r-)-get_sum(i-))*x*y;

         i=r;

     }

     return ans;

 }

 int main()

 {

     Mod=;

     for(LL i=;i<=;i++) Mod*=;

     LL T;

     T=;

     scanf("%d",&T);

     mx=;

     for(LL i=;i<=T;i++)

     {

         scanf("%d%d%d",&t[i].x,&t[i].y,&t[i].a);

         mx=mymax(mx,mymin(t[i].x,t[i].y));

         t[i].id=i;

     }

     sort(t+,t++T,cmp);

     get_mu();

     sort(f+,f++mx,cmp);

     memset(c,,sizeof(c));

     memset(as,,sizeof(as));

     LL now=;

     for(LL i=;i<=T;i++)

     {

         while(f[now].a<=t[i].a&&now<=mx) change(now),now++;

         t[i].ans=get_ans(t[i].x,t[i].y);

     }

     sort(t+,t++T,cmp2);

     for(LL i=;i<=T;i++)

     {

         printf("%d\n",(t[i].ans%Mod+Mod)%Mod);

     }

     return ;

 }

[BZOJ 3529]

2016-09-03 10:57:57

相关文章