题解洛谷P5174 圆点

题外话

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

但是 $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$ 就可以做了

代码

#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);
}

Dilute

题解 洛谷P5174 圆点

题外话

解法

代码

题解洛谷P5174 圆点