我本来自己想到的的做法是跟别的大多数题解一样的
但是L J C 00118 LJC00118 L J C 0 0 1 1 8
首先，我们看到圆上整点，我们可以发现圆上整点的集合就是满足x , y x, y x , y x 2 + y 2 ≤ r 2 x^2 + y^2 \leq r^2 x 2 + y 2 ≤ r 2 ∑ i = 1 r ∑ i 2 + j 2 ≤ r i 2 + j 2 \displaystyle\sum_{i = 1}^{\sqrt r}\sum_{i^2 + j^2 \leq r} i^2 + j^2 i = 1 ∑ r i 2 + j 2 ≤ r ∑ i 2 + j 2
我们把这个式子给化一下
令j j j m a x j maxj m a x j
$ \displaystyle\sum_{i = 1}^{\sqrt r} \frac{maxj(maxj + 1)(2maxj + 1)}{6} + i^2 * maxj$
然后我们瞪一下这个式子，显然可以发现m a x j maxj m a x j
然后我们存一下m a x j maxj m a x j i i i m a x j maxj m a x j
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); }
