题外话 我本来自己想到的的做法是跟别的大多数题解一样的
但是$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); }