一开始跌rating就停不下来了。。。
A,B水题不说了
C.是一道很巧妙的题目。
给出n个数，然后询问两两的gcd*（gcd-1）的和。n<=1W,a[i]<=1W
我考场上只想到了gcd之和怎么求，因为sigma（fai（d）d|n)=d，所以我们只要枚举因数累加欧拉函数即可。
具体来说， 令s[x]表示是x的倍数的a[i]的个数
但是统计gcd*（gcd-1）之和我并没有想到类似于fai的函数。
实际上，这个想法是可以拓展的。既然我们可以统计两两的公因数的某个函数的和，那么我们有f(n)=n*(n-1)
再令f(n)=sigma(g(d) d|n) 那么我们对两两的公因数的g函数求和就可以得到ans。
而由莫比乌斯反演，g[n]=sigma(f(d)*miu(n/d) d|n) 这样就ok了。
（这里需要注意到运用莫比乌斯反演并不需要保证f或g为积性函数，因为在证明中并没有用到积性函数的任何性质）装b装大发了
另外，枚举所有数的因数可以预处理+vector存储做到O（nlogn），就不用O（n√n）了。
此题还有一种做法是容斥原理，类似于 NOI2010能量采集 这道题的想法。
当然那道题用莫比乌斯反演是可以更简单的，但是容斥原理反而给我们此题提供了一种新的做法。
令f[i]表示gcd为i的数的对数，那么我们考虑容斥原理，f[i]=gcd至少为i的对数-gcd为2*i的对数-gcd为3*i的对数。。。
这样我们逆序递推f数组，然后就直接统计答案了。
D.给出一个n个数的数列a,1<=a[i]<=n。然后给出一个k，再给出m个询问（l1，r1，l2，r2）输出满足 l1<=i<=r1,l2<=j<=r2，且a[i]+a[j]==k的（i，j）的个数。n<=3W,m<=3W.
我考场上看到感觉十分难统计和为k的对数的个数，不是什么数据结构能够快速维护的。
这种情况下一般考虑莫队，因为莫队维护一个区间内的和为k的方案数是相当容易的。
而现在要求必须在两个区间，我们考虑如何把两个区间的转化到一个区间里的。
考虑容斥，搬运一下出题人的题解：
定义记号f(A,B)表示询问区间A，B时的答案
评论 (0)
