注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Bzoj2705】【Sdoi2012】【Longge的问题】  

2014-05-09 14:16:43|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    题目大意:求∑gcd(i,n)
    上午去复习以前写过的一些东西去了,然后突然被XXX君叫去看这道题....
    首先n固定了,所以咱们可以枚举n的因数【sqrt(n)解决】,然后咱们只需要求每一个因数作为gcd(i,n)的答案的i的个数即可。gcd(i,n)=k,则gcd(i/k,n/k)=1,咱们只需要求 n/k以内与n互质的数的个数即可。由于n/k依旧可能很大,所以不能直接用线性欧拉筛法。本来考虑用莫比乌斯反演什么的试试乱搞的,但是失败了= =但是这里看到一个比较有趣的数学的东西。那就是狄利克雷卷积。【传送门

    实际上这个的答案就是
    ∑k*phi(n/k) 【k满足 n%k=0】
    然后咱们把k看做一个函数f[k]=k,phi(n/k)看做一个函数 g[k]=phi(k)
    记答案为a[n]=∑f[k]*g[n/k]
    右边这个就是 f[k]和g[k]的狄利克雷卷积。
    然后可以证明的就是 如果 f[k],g[k]均是积性函数的话,那么它们的狄利克雷卷积 a[k]也是积性函数。
    对于积性函数咱们只需要知道它的质因数如何求a[],然后n的答案就是 所有的a[]相乘的结果。
    对于一个质数p,a[p^i]=∑f[p^k]*g[p^(i-k)]
                                    =∑p^k(p^(i-k)-p^(i-k-1))
                                    =∑p^i-p^(i-1)
                                    =(i+1)*p^i-i*p^(i-1)
    然后这个就可以用积性函数的方法做,咱们求出N分解质因数之后每一个质因数的个数,就可以对每一个质因数求一次a[],然后根据积性函数的性质a[]相乘就是最后的答案了0.0复杂度O(sqrt(n))
    然后还可以进一步化简:
    (i+1)*p^i-i*p^(i-1)
  =p^i(i+1-i/p)
  然后最后全部乘起来就是 n*(pi+p-i)/p=n*((p-1)i/p+1) 
  然后就暴力筛O(sqrt(n))以内的质数就可以了。
========================

program bzoj2705;
var ans,n,j,k:int64;
    i:longint;

procedure init;
var i:longint;
begin
  read(n);
  ans:=n;
  for i:=2 to trunc(sqrt(n)) do
   begin
     if n mod i=0 then
      begin
        j:=i;k:=0;
        while n mod i=0 do
         begin
           inc(k);
           n:=n div i;
         end;
        ans:=ans+ans*(j-1)*k div j;
      end;
   end;
  if n<>1 then ans:=ans+ans*(n-1)*1 div n; 
  write(ans);
end;

begin
  init;
end.


  评论这张
 
阅读(353)| 评论(2)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017