4
26
2015
0

BestCoder Round #39

一开始跌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]的个数

   那么for 每个a[i]的因数x ans+=s[x]*fai(x)。
  
   
  直接for1(i,maxn)ans+=s[x]*s[x]*fai(x)即可
  然后不妨认为a[i]和a[j]的gcd为x,那么我们就对所有整除x的y求和了fai(y),而这个和就是x。我们就正确地统计出了所有gcd之和。

  但是统计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时的答案

  用记号+表示集合的并
 
  利用莫队算法我们可以计算出任意f(A,A)的值 
   
  不妨假设A=[l1,r1],B=[l2,r2],C=[r1+1,l2−1]
 
  容易知道f(A,B)=f(A+B+C,A+B+C)+f(C,C)−f(A+C,A+C)−f(C+B,C+B)
 
  因此一个询问被拆成四个可以用莫队算法做的询问
Category: bestcoder | Tags: | Read Count: 522

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

| Theme: Aeros 2.0 by TheBuckmaker.com