题外话

我本来自己想到的的做法是跟别的大多数题解一样的

但是$LJC00118$大仙跟我讲了他的做法,据说常数更小一些,于是我就过来发(水)题(社)解(区)了(分)。

解法

首先,我们看到圆上整点,我们可以发现圆上整点的集合就是满足$x, y$都为整数,且$x^2 + y^2 \leq r^2$的点的集合,那么这题要求的东西就可以表示成
$\displaystyle\sum_{i = 1}^{\sqrt r}\sum_{i^2 + j^2 \leq r} i^2 + j^2$
表达不太规范,反正意思对就行QwQ

我们把这个式子给化一下

令$j​$的上界为$maxj​$
$ \displaystyle\sum_{i= 1}^{\sqrt r} \left(\sum_{j = 1}^{maxj} j^2\right) + i^2 * maxj ​$

$ \displaystyle\sum_{i = 1}^{\sqrt r} \frac{maxj(maxj + 1)(2maxj + 1)}{6} + i^2 * maxj$

然后我们瞪一下这个式子,显然可以发现$maxj​$是单调下降的

然后我们存一下$maxj​$,然后一遍枚举$i​$一边算$maxj​$就可以做了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>

#define ll long long
#define INF 2147483647
#define mod 1000000007

ll powmod(ll a, int b){
ll sum = 1;
while(b){
if(b & 1){
sum *= a;
sum %= mod;
}
a *= a;
a %= mod;
b >>= 1;
}
return sum;
}
ll inv6;

ll sum(ll n){
return (n * (n + 1) % mod * ((n << 1) + 1) % mod) * inv6 % mod;
}

int main(){
inv6 = powmod(6, mod - 2);
ll r;
scanf("%lld", &r);
ll ans = 0;
ll num = sqrt(r) + 1;
for(ll i = 0; i * i <= r; i++){
while(i * i + num * num > r)
num--;
ans += i * i % mod * num % mod;
ans %= mod;
ans += sum(num);
ans %= mod;
}
ans <<= 2;
ans %= mod;
printf("%lld\n", ans);
}

 评论