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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Bzoj1257】【Cqoi2007】【余数之和】  

2014-05-04 15:40:23|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    题目大意:给出(n,k),求 ∑(n mod i) (1<=i<=k)
    n,k<=10^9

    看到很多人交了这道题,所以咱也跑去搅一搅=w=
    0.0首先对于n<k的情况,咱们可以把它转化成两部分,一部分是 n<=i,一部分是n>i,然后对于n<=k的部分,咱们易知道都是n本身,所以O(1)可以搞定,问题就是n<=i的情况,咱们需要计算的实际上就是这部分。

    n mod i实际上可以写成 n-i*k【限制:0<=n-i*k<i】,每一个i可以找到一个对应的k即n div i,咱们会发现这些相同k的i构成了一个连续区间,咱们枚举k的范围,就可以得到不同的i的连续区间。

    容易知道k的取值只有sqrt(n)种【关于这个的证明..实际上咱们有k=n div i,然后n div i的取值最多有sqrt(n)种,关于为什么n div i的取值是sqrt(n)种,咱们对于 i<sqrt(n)有sqrt(n)种取值,然后i>=sqrt(n) n div i在sqrt(n)内,所以也只有sqrt(n)种取值】

    所以所有的i的范围只有O(sqrt(n))种,咱们可以O(sqrt(n))枚举出这些区间,然后对于每一个区间的所有i,它们的余数实际上是一个等差序列。所以可以直接O(1)求出来。然后关于如何O(sqrt(n))枚举出n div i的所有满足条件的K的值,可以先去做一做bzoj2301恩0.0
    关于这一道题为什么是等差序列0.0咱们可以围观出,n-i*k,对k不变,i调到i+1的时候,n-(i+1)*k,它们的余数相差k,一直到n-j*k为负数的时候到顶。

============================

program bzoj1257;
var n,k:longint;
    ans:int64;

procedure init;
var i,la,r,l:longint;
begin
  read(n,k);
  ans:=0;
  if k<n then
   begin
     ans:=ans+int64(k)*int64((n-k));
     n:=k;
   end;
  i:=1;
  while i<=n do
   begin
     la:=k div (k div i);
     if la>n then la:=n;
     l:=k mod i;r:=k mod la;
     ans:=ans+int64((r+l))*int64((la-i+1)) shr 1;
     i:=la+1;
   end;
  write(ans);
end;

begin
  init;
end.


  评论这张
 
阅读(19)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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