【题解】P5172 Sum

· · 题解

简单类欧题，给定 n,r 求：

\sum_{d=1}^{n}(-1)^{\left\lfloor d\sqrt{r} \right\rfloor}

如果 r 能开出来就太好了，可惜不一定可以，所以我们需要推式子。

简单处理

当 \sqrt r\equiv 0\pmod 2 那么答案就是 n，因为一共是 n 个 1 相加，如果 \sqrt r\equiv 1\pmod 2，那么答案就要考虑 n 的奇偶性，如果 n 是偶数就输出 0 否则输出 -1。

那如果 \sqrt r 开出来是一个无理数怎么办呢？

考虑 -1 次幂的最基本推导：(-1)^{2n}=1，那么就可以写出式子 (-1)^x=1-2(x\bmod 2)。而考虑取余运算的基本定义，我们可以写出：

(-1)^x=1-2\left(x-2\left\lfloor\dfrac{x}{2}\right\rfloor\right)=1-2x+4\left\lfloor\dfrac{x}{2}\right\rfloor

将这个式子代入到原式之中，就得到：

\sum_{d=1}^{n}1-2\left\lfloor d\sqrt{r} \right\rfloor+4\left\lfloor\dfrac{\left\lfloor d\sqrt{r} \right\rfloor}{2}\right\rfloor

将其中无关紧要的部分写开来，就是：

n+2\sum_{d=1}^{n}\left\lfloor d\sqrt{r} \right\rfloor+4\sum_{d=1}^{n}\left\lfloor\dfrac{d\sqrt{r}}{2}\right\rfloor

接下来就是类欧的重头戏了。

类欧化简

设 f(a,b,c,n)=\sum\limits_{i=1}^{n}\left\lfloor\dfrac{a\sqrt r+b}{c}\cdot i\right\rfloor，那么题目所求就是：

n-2f(1,0,1,n)+4f(1,0,2,n)

不妨令 x=\sqrt r，t=\dfrac{ax+b}{c}，更方便地表示这个式子：

f(a,b,c,n)=\sum\limits_{i=1}^{n}\left\lfloor ti\right\rfloor

然后就可以分类讨论。

分类讨论

我们对于 t 的大小进行简单的考虑。

若 t\ge 1：

记 \lfloor t\rfloor 为 \alpha 那么就可以写出：

f(a,b,c,n)=\sum\limits_{i=1}^{n}\left\lfloor ti\right\rfloor=\sum\limits_{i=1}^{n}\left\lfloor ti-\alpha i+\alpha i\right\rfloor

将 t 值代入进去就得到：

\dfrac{(n+1)n}{2}\alpha+\sum\limits_{i=1}^{n}\left\lfloor\left(\dfrac{ax+b}{c}-\alpha\right)i\right\rfloor

不难发现，式子中 \alpha 移到分母上之后就得到了该式子的递归化简式：

f(a,b-c\alpha,c,n)+\dfrac{(n+1)n}{2}\alpha

若 t<1：

那么，由于 t 的正负性，不难发现 \alpha 就应该为 0，那么我们可以利用贡献思想进行一个简单的推论：

f(a,b,c,n)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{\left\lfloor{nt}\right\rfloor}\left[j<ki\right]

然后在谓词函数里做一个简单的代数变换：

f(a,b,c,n)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{\left\lfloor{nt}\right\rfloor}\left[\dfrac{j}{t}<i\right]

然后调换求和顺序：

\sum\limits_{j=1}^{\left\lfloor{nt}\right\rfloor}\sum\limits_{i=1}^{n}\left[i>\dfrac{j}{t}\right]

这样意义是将限制条件转换到内部的和式之中，从而达到化简的目的：

\sum\limits_{j=1}^{\left\lfloor{nt}\right\rfloor}\left(n-\left\lfloor\dfrac{j}{t}\right\rfloor\right)

这时候如果将 t 值代入，很有意思的情况就会出现：

\sum\limits_{j=1}^{\left\lfloor{nt}\right\rfloor}\left(n-\left\lfloor\dfrac{j}{\dfrac{ax+b}{c}}\right\rfloor\right)

化为正常形式：

\sum\limits_{j=1}^{\left\lfloor{nt}\right\rfloor}\left(n-\left\lfloor\dfrac{j}{ax+b}\cdot c\right\rfloor\right)

将 j 和 c 的位置互换，然后把 n 提出来：

n\cdot \left\lfloor{nt}\right\rfloor-\sum\limits_{j=1}^{\left\lfloor{nt}\right\rfloor}\left\lfloor\dfrac{c}{ax+b}\cdot j\right\rfloor

右边是什么？是非常接近最初形式的一个式子，考虑将他化成最初形式，乘上分母的共轭：

n\cdot \left\lfloor{nt}\right\rfloor-\sum\limits_{j=1}^{\left\lfloor{nt}\right\rfloor}\left\lfloor\dfrac{c(ax-b)}{(ax+b)(ax-b)}\cdot j\right\rfloor n\cdot \left\lfloor{nt}\right\rfloor-\sum\limits_{j=1}^{\left\lfloor{nt}\right\rfloor}\left\lfloor\dfrac{cax-cb}{a^2x^2-b^2}\cdot j\right\rfloor

这已经很接近结果了，但是我们考虑到 x^2 是等同于 r 的，于是写作：

n\cdot \left\lfloor{nt}\right\rfloor-\sum\limits_{i=1}^{\left\lfloor{nt}\right\rfloor}\left\lfloor\dfrac{cax-cb}{a^2r-b^2}\cdot i\right\rfloor

写成一般形式：

f(a,b,c,n)=n\cdot \left\lfloor{nt}\right\rfloor-f(ca,-cb,a^2r-b^2,\left\lfloor{nt}\right\rfloor)

所以我们已经得到答案了，所以我们能够很容易写出代码。

代码实现

代码实现的一些细节在于，我们应当要把下取整部分提前算出，否则在式子的运算中会到最后才进行下取整。

#include<bits/stdc++.h>
#define int long long
using namespace std;
double x;
int T,n,r;
int f(int a,int b,int c,int n){
    if(n==0)return 0;
    int gcd=__gcd(a,__gcd(b,c));
    a/=gcd,b/=gcd,c/=gcd;
    int t=(a*x+b)/c;
    if(t!=0)return n*(n+1)/2*t+f(a,b-c*t,c,n);
    else{
        int kn=(a*x+b)*n/c;
        return n*kn-f(a*c,-b*c,a*a*r-b*b,kn);
    }
}signed main(){
    scanf("%lld",&T);
    while(T--){
        scanf("%lld%lld",&n,&r);
        x=sqrt(r);
        int s=(int)x;
        if(s*s==r){
            if(s%2==0)printf("%lld\n",n);
            else if(n%2==0)puts("0");
            else puts("-1");
        }else printf("%lld\n",n-2*f(1,0,1,n)+4*f(1,0,2,n));
    }return 0;
}