«
»

[OI][Vijos 1214]伤心的AsukaNoKaze

这题算是个数论题。

其实也没用到什么数论结论，首先手算找找规律。发现，对于 \forall x\in (\frac{n}{i+1},\frac{n}{i+1}],x\in {\mathbb Z} 有 n ~{\mathtt div}~ x 为常数i - 1，于是这一区间内的数就可以只算一次，然后将结果乘以区间内整数的个数就行了。但当i>\sqrt{n}时，每个区间的长度\frac{n}{i}-\frac{n}{i-1}<1，这样就得不偿失了，所以当i<=\sqrt{n}时每个区间处理一次，当i>\sqrt{n}时，进行朴素的计算。

div 运算就这样解决了，剩下的取余可以由整除的结果生成，对于\forall x\in {\mathbb Z}，有n ~{\mathtt mod}~ i = n - i(n ~{\mathtt div}~ i)，每个区间内，n ~{\mathtt div}~ i为定值，所以令first=\frac{n}{i+1},last=\frac{n}{i},k=n ~{\mathtt div}~ i=i-1，则对于区间(first,last]，有\sum\limits_{i=first}^{last}{n ~{\mathtt mod}~ i}=\sum\limits_{i=first}^{last}{n- i(n ~{\mathtt div}~ i)}=\sum\limits_{i=first}^{last}{n-i\cdot{}k}=n\cdot{}(last-first)-k\sum\limits_{i=first}^{last}{i}=n\cdot{}(last-first)-k\frac{\cdot{}(first+1+last)(last-first)}{2}=n\cdot{}(last-first)-\frac{(first+1+last)(last-first)(i-1)}{2}。同样地，当i>\sqrt{n}时，进行朴素的计算。

时间复杂度 O(\sqrt{n})，空间复杂度 O(1)。

算法就是这样了，刚开始写的时候 TLE 了，原因是作为循环条件的 sqrt(n) 没有提前计算出来，于是导致了很多不必要的运算，多么低级的错误……

C++ 代码在这里。

P.S. 突然想做编号是大家生日的题目，这题编号是我一个朋友的生日，自己的生日编号的题目的状态是暂不提供……

Tags:,,,

Related Posts

Tags: , , ,

This entry was posted on Sunday, October 19th, 2008 at 10:17 pm and is filed under Information Technology. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

3 Responses to “[OI][Vijos 1214]伤心的AsukaNoKaze”

  1. Jason911 says:
    October 20, 2008 at 11:31 am

    Orz神牛太强了

  2. 醉倚西风 says:
    October 22, 2008 at 12:07 am

    @@@@@@@@@@@@头晕

  3. Doggie says:
    October 25, 2008 at 6:19 pm

    额... 你好牛啊...
    我是 doglish.cn 的博主...
    有空注册一个 Plurk 吧，我的是 plurk.com/doggie
    用这个注册可以自动成为我的跟随者。

Leave a Reply