题解 P5174 【圆点】

love_luke · 2019-01-13 14:15:58 · 题解

对HAY大佬的题解做一个进一步的解释（我觉得他没说清楚）

首先，这道题的数据还是比较大的，感觉用long long也会爆，先不管，开成long long。然后读入r,半径是根号r，就开个方，存在lin里。

    long long r,i,sum=0,lin,a,b;
    scanf("%lld",&r);
    lin=sqrt(r);

然后就到了精髓部分。其他题解都用了平方和公式，而我们不需要，使用远古算法，把每个平方的个数都求出来，然后乘起来，最后全部加起来。当然，我们只需要算一个象限加一个半轴的，最后再乘4就行了。

    for (i=1;i<=lin;++i)
    {
        a=sqrt(r-i*i);//当横坐标为i时，第一象限内最多有多少个
        a=(2*a+1)%1000000007;//把半轴和纵坐标为i的情况算上
        b=(i*i)%1000000007;//平方
        sum=(sum+a*b)%1000000007;//个数乘平方再累加
    }
    printf("%lld",(sum*4)%1000000007);//输出