OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【SDOI2014】数表

【题目描述】

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

【输入】

输入包含多组数据。 
输入的第一行一个整数Q表示测试点内的数据组数,接下来Q行,每行三个整数n,m,a描述一组数据。

【输出】

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

【输入样例】

2

4 4 3

10 10 5

【输出样例】

20

148

【数据范围】

对于30%的数据,1<=n,m<=400,1<=Q<=200
对于另外30%的数据,1<=n,m<=10^5,1<=Q<=10
对于100%的数据,1<=n,m<=10^5,1<=Q<=20000,0<=a<=10^9

【题解】

要求的式子很裸,我们先不考虑a的限制,直接进行化简:


其中很明显是积性函数,可以通过线性筛来预处理,计算前缀和,然后再对剩余部分进行分块,就能够得到一个单次询问O(sqrt(n))的优秀算法。

现在考虑a的限制,我们发现只有时对答案有贡献,所以我们可以离线处理,按照每个询问的a从小到大排序,这样在处理前面的询问时,大于a的值可以先不累加。用一个树状数组进行维护,就能够快速得到前缀和了。

【代码】

数论好难啊_(:зゝ∠)_

http://paste.ubuntu.com/10588245/

评论

© OI技术宅 | Powered by LOFTER