[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: , , ,

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

  1. Jason911 says:

    Orz神牛太强了

  2. 醉倚西风 says:

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

  3. Doggie says:

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

Leave a Reply