【BZOJ 3529】 [Sdoi2014]数表

3529: [Sdoi2014]数表Time Limit:10 SecMemory Limit:512 MBSubmit:411Solved:245[Submit][Status][Discuss]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

24 4 310 10 5

Sample Output

20148

HINT

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

Source

Round 1 Day 1

莫比乌斯反演+树状数组。

首先求出f[i]表示能整除i的所有自然数之和。

以下来自PoPoQQQ的ppt。（P20）

大概的思路是：

1.先不考虑a的限制：

经过变形，最后的式子是：

前面一部分：好多连续的不同的d，n/d和m/d都是不变的，可以一起计算，时间为O(nsqrt(n))

后面一部分：在预处理的时候，枚举i的倍数，，加到对应的d中；然后求出前缀和。预处理复杂度O(nsqrt(n))

但是，有了a的限制怎么办？

离线来做：

把询问按照a从小到大排序，f[]也从小到大排序，那么对于一个询问来说，要计算的是f[i]<=a的i。

使用树状数组维护sigma(f[i]*u(d/i))的前缀和，每次插入小于当前a的f[i]（并嵌套上对于d的循环），然后询问前缀和即可。

#include <iostream>#include <algorithm>#include <cmath>#include <cstring>#include <cstdio>#define M 100000using namespace std;pair<int,int> f[M+5];int t[M+5],p[M],mu[M+5],ans[M+5],check[M+5],T;struct Q{int n,m,a,id;}q[M];bool cmp2(Q a,Q b){return a.a<b.a;}void Getmobius(){mu[1]=1;int tot=0;for (int i=2;i<=M;i++){if (!check[i]){p[++tot]=i;mu[i]=-1;}for (int j=1;j<=tot;j++){if (i*p[j]>M) break;check[i*p[j]]=1;if (i%p[j]==0){mu[i*p[j]]=0;break;}else mu[i*p[j]]=-mu[i];}}}void Getf(){for (int i=1;i<=M;i++)for (int j=i;j<=M;j+=i)f[j].first+=i;for (int i=1;i<=M;i++)f[i].second=i;sort(f+1,f+1+M);}int lowbit(int x){return x&(-x);}void Update(int x,int k){for (int i=x;i<=M;i+=lowbit(i))t[i]+=k;}int Getsum(int x){int ans=0;for (int i=x;i;i-=lowbit(i))ans+=t[i];return ans;}int Query(int n,int m){int ans=0,pos;if (n>m) swap(n,m);for (int i=1;i<=n;i=pos+1){pos=min(n/(n/i),m/(m/i));ans+=(n/i)*(m/i)*(Getsum(pos)-Getsum(i-1));}return ans&0x7fffffff;}int main(){Getmobius();Getf();scanf("%d",&T);for (int i=1;i<=T;i++)scanf("%d%d%d",&q[i].n,&q[i].m,&q[i].a),q[i].id=i;sort(q+1,q+1+T,cmp2);int j,i;for (i=1,j=1;i<=T;i++){for (;j<=M&&f[j].first<=q[i].a;j++)for (int k=f[j].second;k<=M;k+=f[j].second)Update(k,f[j].first*mu[k/f[j].second]);ans[q[i].id]=Query(q[i].n,q[i].m);}for (int i=1;i<=T;i++)printf("%d\n",ans[i]);return 0;}

感悟：

莫比乌斯函数在使用时，要对sigma套sigma进行变形：如果后一个sigma中的某一个数与这个sigma的循环变量无关，那么可以提到前面去

每个人在他的人生发轫之初，总有一段时光，