P3312 [SDOI2014]数表

啊啊啊我昨天怎么没写题解wwww

补昨日题解。。。

题目链接 : https://www.luogu.org/problemnew/show/P3312

也是莫反 我要把fft留到今天写

【和zyn小可爱约好了 明天不填完坑就请她cafeking哦

表面题意:很明显了。。。

有一张N*m的数表,其第i行第j列(1 < =i < =n,1 < =j < =m)的数值为能同时整除i和j的所有自然数之和。

给定a,计算数表中不大于a的数之和。

第一步 : 每个格子里的那个东西是什么?

整除i和j的所有自然数之和

↓                ↓

gcd(i, j)        因数和

是 sigma(gcd(i, j))

sigma(x)表示x的因数和

现在的题意:

有一张n * m的数表,给定a,计算数表中不大于a的sigma(gcd(i, j))之和。

蒟蒻认为 看到gcd 又看到计数 就可以往莫反上靠靠了

P3312 [SDOI2014]数表

另 这样在线做会超时的

由于随着a变大

变化仅为f[] 中的一些值由零变一

所以把询问按a排序

每次补齐卷积

详见代码work部分

代码:

几个要注意的细节【大佬自动无视】:

1)sigma不是单调递增 所以请排序

2)由于本题取模数十分毒瘤 所以随便爆int~

3)sigma并不是所有项都符合积性函数性质 所以要O(n ln n)筛

4)now注意上界 a可能很大但用不上

上一篇:CoreGraphics-线段常见属性及渲染模式介绍


下一篇:浅谈flex布局中小技巧