# 抛出问题

$$\sum^{B} _ {i=A}\sum^{i} _ {j=1}\left \lfloor \frac{i}{j} \right \rfloor \times \left ( -1\right )^j$$

# 题目解答

## 比赛解答

$O(\sqrt{B})$的原创解答在本博客最下面。

### 冷静分析

$$\sum^{B} _ {i=A}\sum^{i} _ {j=1}\left \lfloor \frac{i}{j} \right \rfloor \times \left ( -1 \right )^j =\sum^{B} _ {i=1}\left ( \left ( -1 \right )^i \sum^{B} _ {j=A} \left \lfloor \frac{j}{i} \right \rfloor \right )$$

$$\sum^{B} _ {i=1}\left ( \left ( -1 \right )^i \sum^{B} _ {j=A} \left \lfloor \frac{j}{i} \right \rfloor \right ) =\sum^{B} _ {i=1}\left ( \left ( -1 \right )^i \left ( \sum^{B} _ {j=1} \left \lfloor \frac{j}{i} \right \rfloor – \sum^{A-1} _ {j=1} \left \lfloor \frac{j}{i} \right \rfloor \right ) \right )$$

$$0,0,1,1,1,2,2,2,3,3,3,\cdots$$

### 程序实现

#include <cstdio>
int main()
{
int a, b;
long long ans = 0, r, s, t;
scanf("%d%d", &a, &b);
for(register int i = 1; i <= b; i += 1)
{
r = a / i - 1;//因为最后一项长度不定，所以我们确定倒数第二项
s = (a - r * i - i) * (r + 1);//计算最后一项的长度并求和
r = (r + 1) * r / 2 * i;//前面项的和
t = s + r;
//同理可得
r = (b + 1) / i - 1;
s = (b + 1 - r * i - i) * (r + 1);
r = (r + 1) * r / 2 * i;
if(i & 1)
ans -=  s + r - t;
else
ans += s + r - t;
}
printf("%lld", ans);
return 0;
}


## 极速解法（原创）

### 冷静分析

$$\sum^{B} _ {i=1}\left ( \left ( -1 \right )^i \left ( \sum^{B} _ {j=1} \left \lfloor \frac{j}{i} \right \rfloor – \sum^{A-1} _ {j=1} \left \lfloor \frac{j}{i} \right \rfloor \right ) \right ) =\sum^{B} _ {i=1}\left ( \left ( -1 \right )^i \sum^{B} _ {j=1} \left \lfloor \frac{j}{i} \right \rfloor \right ) – \sum^{A-1} _ {i=1}\left ( \left ( -1 \right )^i \sum^{A-1} _ {j=1} \left \lfloor \frac{j}{i} \right \rfloor \right )$$

### 程序实现

#include <cstdio>

int a, b;

//对比 O(B) 的代码，其实只是加了一些高斯求和罢了
inline long long getans(int f)
{
int rr, q, delta;
long long ans = 0, r, r_, s, t, l;
for(register int i = (f ? 1 : 2); i <= a; i = q + 2)
{
rr = a / i;
q = a / rr;
if((q & 1) && !f)//要偶数却是奇数
q ^= 1;
else if(!(q & 1) && f)//要奇数却是偶数
q -= 1;
delta = (q - i >> 1) + 1;//中间长度
r = a / i - 1;//因为最后一项长度不定，所以我们确定倒数第二项
l = a + 1 - r * i - i;
s = (r + 1) * (l - (delta - 1) * (r + 1)) * delta;
//分块的最后一项求和
r_ = r;//记录
r = (r + 1) * r * i >> 1;//前面项的和
r = r * delta + ((1 + r_) * r_ >> 1) * ((delta - 1) * delta);
//增加的值
t = s + r;
if(f & 1)
ans += t;
else
ans -= t;
}
for(register int i = (f ? 1 : 2); i <= b; i = q + 2)
{
rr = b / i;
q = b / rr;
if((q & 1) && !f)//要偶数却是奇数
q ^= 1;
else if(!(q & 1) && f)//要奇数却是偶数
q -= 1;
delta = (q - i >> 1) + 1;//中间长度
r = b / i - 1;//因为最后一项长度不定，所以我们确定倒数第二项
l = b + 1 - r * i - i;
s = (r + 1) * (l - (delta - 1) * (r + 1)) * delta;
//分块的最后一项求和
r_ = r;//记录
r = (r + 1) * r * i >> 1;//前面项的和
r = r * delta + ((1 + r_) * r_ >> 1) * ((delta - 1) * delta);
//增加的值
t = s + r;
if(f & 1)
ans -= t;
else
ans += t;
}
return ans;
}

int main()
{
scanf("%d%d", &a, &b);
a -= 1;
printf("%lld", getans(1) + getans(0));
return 0;
}


# 写在最后

### 5 条评论

您 tql，%%%%%

#### boshi · 2018年8月24日 7:14 下午

“ 严格来说，根号外面至少还有 4 的常数，但是似乎还有可以优化的地步” 请问似乎指的到底是哪里呢？

#### EternalTron · 2018年9月5日 9:11 下午

今天才看到，没及时回复你，抱歉。
我认为 “似乎还有可以优化的地步” 指的是常数优化，我们可以发现有的部分是具有高度相似性的，因此还有合并的地步。

#### XZYQvQ · 2018年9月5日 9:42 下午

Orz 好久不见啊 QAQ
不知道您还会不会来一中呀？
QvQ