[SDOI2014]数表

题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

20

148

说明

1 < =N．m < =10^5 ， 1 < =Q < =2*10^4

题解：

令F[i]为i的因数和,g[i]为gcd=i的数量

则ans=∑∑F[gcd(i,j)]

=∑_dF[d]g[d]

g[d]=∑_i∑_j[gcd(i,j)==d] (i<=n,j<=m)

　 =∑∑[gcd(i,j)==1] (i<=n/d,j<=m/d)

=∑∑∑_pμ(p) (p|i,p|j)

=∑_pμ(p)∑∑1 (p<=n/d,i<=n/dp,j<=m/dp)

=∑_pμ(p)[n/dp][m/dp]

ans=∑_dF[d]∑_pμ(p)[n/dp][m/dp]

令k=dp

g[d]=∑_k[n/k][m/k]μ(k/d) (k<=n，d|k)

ans=∑_k[n/k][m/k]∑_dF[d]μ(k/d) (d|k)

令f[k]=∑_dF[d]μ(k/d) (d|k)

处理处f的前缀和就行了，对于每个F[i],把它的f[x*i]全部加上F[i]*mu[x]

至于小于a的条件，离线按a排序，将F按从小到大顺序加入维护

分块就不说了

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 struct data

 {

     int id,n,m,a;

 }a[];

 int Mod=(<<);

 int f[],mu[],ms[],prime[],tot;

 int c[],p[],now=,ans[];

 bool vis[];

 bool cmp2(data a,data b)

 {

     return a.a<b.a;

 }

 bool cmp(int a,int b)

 {

     return f[a]<f[b];

 }

 void mobius()

 {int i,j;

     mu[]=;

     ms[]=;f[]=;

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

     {

         if (vis[i]==)

         {

             mu[i]=-;

             f[i]=i+;

             ms[i]=i;

             prime[++tot]=i;

         }

         for (j=;j<=tot,prime[j]*i<=;j++)

         {

             vis[i*prime[j]]=;

             if (i%prime[j])

             {

                 ms[i*prime[j]]=prime[j];

                 f[prime[j]*i]=f[i]*f[prime[j]];

                 mu[i*prime[j]]=-mu[i];

             }

             else

             {

                 ms[prime[j]*i]=ms[i]*prime[j];

                 if (ms[i]==i) f[prime[j]*i]=(ms[prime[j]*i]*prime[j]-)/(prime[j]-);

                 else f[prime[j]*i]=f[i/ms[i]]*f[prime[j]*ms[i]];

                 mu[i*prime[j]]=;

                 break;

             }

         }

     }

 }

 void add(int x,int d)

 {

     while (x<=)

     {

         c[x]+=d;

         x+=(x&(-x));

     }

 }

 int query(int x)

 {

     int s=;

     while (x)

     {

         s+=c[x];

         x-=(x&(-x));

     }

     return s;

 }

 void solve(int x)

 {int j,pos,i,lasts,ss;

     for (;f[p[now]]<=a[x].a;now++)

     {

         for (j=;p[now]*j<=;j++)

         add(p[now]*j,f[p[now]]*mu[j]);

     }

     pos=;

     lasts=;

     for (i=;i<=a[x].n;i=pos+)

     {

         pos=min(a[x].n/(a[x].n/i),a[x].m/(a[x].m/i));

         ss=query(pos);

         ans[a[x].id]=(ans[a[x].id]+(a[x].n/i)*(a[x].m/i)*(ss-lasts));

         //cout<<ans[a[x].id]<<' ';

         lasts=ss;

     }

     while (ans[a[x].id]<) ans[a[x].id]+=Mod;

     //cout<<endl;

 }

 int main()

 {int T,i,j;

     cin>>T;

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

     {

       scanf("%d%d%d",&a[i].n,&a[i].m,&a[i].a);

       if (a[i].n>a[i].m) swap(a[i].n,a[i].m);

         a[i].id=i;

     }

      mobius();

      for (i=;i<=;i++) p[i]=i;

       sort(p+,p+,cmp);

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

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

      solve(i);

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

      printf("%d\n",ans[i]);

 }

题目描述

输入输出格式

输入输出样例

说明

相关文章