P5172 Sum 题解


以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • Qingyu
    等等我第一个sgn函数里面的内容写错了-。-那个1和-1的位置需要交换一下qwq
  • skkyk
    %
  • GKxx
    orz qingyu dalao tql!!!
作者: Qingyu 更新时间: 2019-01-03 22:16  在Ta的博客查看 举报    5  

菜鸡刚做完类欧几里得板子又来一题……

前置姿势

类欧几里得算法的思想(厚颜无耻贴上自己的题解qwqhttps://www.luogu.org/blog/shiqingyu/solution-p5170)

题意

多组询问,求 $$\sum^n_{d=1}(-1)^{\left\lfloor d\sqrt r\right\rfloor}$$ (又一道bzoj原题还行)

做法

显然遇到数学题我们应该先打个暴力

然后我们考虑指数上的这个东西,显然$\sqrt r$可能是无理数,做乘法的时候,什么时候进到下一个整数会十分自闭,因此显然不是让我们把这个根号拆开。

在初中,我们学习了底数为负数时,幂的符号法则,显然可得

$$\mathrm {sgn}\; (-N)^n=\begin{cases}-1&p=2k,k\in\mathbb Z\\1&p=2k-1,k\in\mathbb Z\end{cases},\forall N>0$$

因此,和式内的东西,可以简单看作“当$d\sqrt r$为偶数时,值为1,否则为-1”

那么,原式显然可以写作

$$I=\sum^n_{d=1}1-2\left(\left\lfloor d\sqrt r\right\rfloor\bmod 2\right)$$

由初等事实$a\bmod p = a-p\left\lfloor\frac{a}{p}\right\rfloor$,不难看出

$$I=\sum^n_{d=1}1-2\left(\left\lfloor d\sqrt r \right\rfloor-2\left\lfloor\frac{d\sqrt r}{2}\right\rfloor\right)=n-2\sum^n_{d=1}\left\lfloor d\sqrt r\right\rfloor + 4\sum^n_{d=1}\left\lfloor\frac{\left\lfloor d\sqrt r\right\rfloor}{2}\right\rfloor$$

当$r$为完全平方数时,这个式子就是一个普及组水题,但是$r$并不一定是完全平方数,所以我们需要考虑如何处理这个式子。

注意到这个和式的几何意义,$d$为内部$y=d\sqrt r$的自变量,且进行了取整操作,而$d$又遍历了所有整点,因此它看起来非常像一个“取整积分”。然而又与$S={\large\int}f(x)\mathrm dx$不同,其所计入数据的仅仅是整点,无法使用Newton - Leibniz公式化简。因此我们考虑其他方法。

在我们计算形如$\sum \left\lfloor \psi(x) \right\rfloor$时,很容易想到两个非常厉害的工具,一个是整除分块,另一个就是类欧几里得。显然这个式子中$r$是无理数,数论分块无法找到对应的区间,很自闭。因此我们考虑类欧几里得。

设函数$y=F(x)=\sqrt rx$。根据类欧几里得的模板,很容易想到$\sqrt r=\frac{A\sqrt r+B}{C}$。容易证明$A,B,C$一定存在,例如取$A=p_0,B=0,C=p_0$就一定是一组合法的解。

由于在类欧几里得的时候我们需要限定$r$的取值,因此我们分两类讨论:

若$\sqrt r=\frac{A\sqrt r+B}{C}>1$

则显然由以下初等事实 $$\left\lfloor q+N \right\rfloor=N+\left\lfloor q\right\rfloor, \forall N\in\mathbb N, q\in \mathbb R$$ 可知原式子可写作 $$\sum ^n_{d=1}\left\lfloor d\sqrt r\right\rfloor =\sum^n_{d=1}\left\lfloor d\left(\frac{A\sqrt r+B}{C}-\left\lfloor\frac{A\sqrt r+B}{C}\right\rfloor\right) \right\rfloor+\sum^n_{d=1}d\left\lfloor\frac{A\sqrt r+B}{C}\right\rfloor$$ $$=\sum^n_{d=1}\left\lfloor d\left(\frac{A\sqrt r+B}{C}-\left\lfloor\frac{A\sqrt r+B}{C}\right\rfloor\right) \right\rfloor+\frac{d(d+1)}{2}\left\lfloor\sqrt r\right\rfloor$$

令$\sqrt {r'}=\left(\frac{A\sqrt r+B}{C}-\left\lfloor\frac{A\sqrt r+B}{C}\right\rfloor\right)$,则显然有$0<\sqrt{r'}<1$(因为有显然结论:$X-1<\left\lfloor X\right\rfloor < X $)。由于后面的余项我们可以$O(1)$的计算出来,因此我们只需要求 $$\sum^n_{d=1}\left\lfloor d\sqrt{r'}\right\rfloor$$ 这样,我们就把$\sqrt r>1$的情况转化为了$0<\sqrt r <1$的情况。

若$0 < \sqrt r = \frac{A\sqrt r+b}{c} < 1$

这时看起来没有任何思路可以做,不妨会想到我们刚才设的函数$f(x)$,画出它的图像(下图中的红色曲线),根据您的数学直觉,不难想到要求出$f^{-1}(x)$(下图中的蓝色曲线)

显然,对于$l_1: y=f(x)$上的点$P'$,做出它在$x$轴上的投影$P$,并以$O$为圆心,$OP$为半径,作圆交$y$轴正半轴于点$Q$,并分别作$QQ'\bot y-\mathrm{axis}$,交$l_2: y=f^{-1}(x)$于点$Q'$。我们定义$\chi(\triangle \beta)$表示$\triangle \beta$所覆盖的整点个数,则显然有 $$\chi(\triangle OPP')=\chi(\triangle OQQ')$$ 而这时,再作$AQ\bot x-\mathrm{axis}$,交于点$A$,显然 $$\chi(\triangle OPP')=\chi(\triangle OQQ')=\chi(\triangle OAQ')$$

而且,不难看出我们不需要考虑这条直线上的点!为什么?因为$y=f(x)$与$y=f^{-1}(x)$所反映的都是一条斜率为无理数的直线,由数论事实告诉我们: $$\forall a\in\mathbb Q, b\in \mathbb R \backslash \mathbb Q, \mathrm {s.t.} b\ne 0 \text{有}ab\notin \mathbb Q$$ 因此直线上不具有任何非平凡有理点,更不可能有整数点。因此结论是显然成立的。

下面,我们考虑反函数的性质 $$f(f^{-1}(x))=x$$ 立即可以知道$f^{-1}(x)=\frac{1}{\sqrt r}x= \frac{Cx}{A\sqrt r+B}$。对斜率$k$进行有理化得到: $$k=\frac{C}{A\sqrt r + B}=\frac{C(A\sqrt r-B)}{(A\sqrt r + B)(A\sqrt r - B)}=\frac{AC \sqrt r-BC}{A^2r-B^2}$$ 同时由反函数的性质,很简单就可以得出$OA=f(AQ')=\left\lfloor AQ'\times \frac{A\sqrt r + B}{C} \right\rfloor$,因此此问题显然可化为规模更小的子问题。

此时,如果令$A'=AC, B'=BC, C'=A^2r-B^2$,就可以转化为另一个子问题。

但是,这杨一直迭代下去,能不能转化为规模更小的子问题?

这个证明是十分显然的,您不妨可以试着证明一下。

提示:考虑变化后的$r$,思考它会落在哪一个范围内,并证明它再一次落入区间$(0,1)$后,一定不会转化为比上一次规模更大的子问题

评论

  • 还没有评论
作者: Great_Influence 更新时间: 2019-01-05 16:22  在Ta的博客查看 举报    1  

首先,特判$\sqrt{r}$是有理数的情况。

然后,因为$(-1)^x=\begin{cases}-1&,x\bmod 2=1\\1&,otherwise\end{cases}$

所以$(-1)^x=1-2(x\bmod 2)=1-2(x-2\lfloor\frac{x}{2}\rfloor)$

因此,答案可化为 $$n-2\sum_{d=1}^n \lfloor d\sqrt r\rfloor +4\sum_{d=1}^n \lfloor\frac{d\sqrt r}{2}\rfloor$$

设$f(a,b,c,n)=\sum_{i=1}^n \lfloor i*\frac{a\sqrt r+b}{c}\rfloor$。

我们可以考虑进行以下步骤:

  1. 去掉后面无理数整数部分产生的贡献。
  2. 将函数关于横纵坐标翻转,然后统计新函数以下的点数,容斥求解。

具体来说,我们先将答案加上 $$\frac{n(n+1)\lfloor\frac{a\sqrt{r}+b}{c}\rfloor}{2}$$

然后,函数变为:

$$f(a,b-\lfloor\frac{a\sqrt{r}+b}{c}\rfloor*c,c,n)$$

因为斜率只有小数部分,因此明显在$(0,1)$内。因此,这个函数的值域比定义域要小。

于是,我们取这个函数的反函数。可以知道,此时需要统计的答案为反函数以左部分的点数。以左不好统计,我们统计以下的,然后容斥减掉。

每操作一次定义域会乘上当前斜率的小数部分。可以知道这个过程不会过多,可以视为$O(\log n)$。因为翻转过程$a,b,c$可能变为平方级,因此每次需要上下同时取gcd。时间复杂度为$O(\log n\log \omega)$($\omega$为值域,$\le 10^{18}$)。

代码:


static int n,r;

static double R;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

ll getans(ll a,ll b,ll c,int n)
{
    if(!n)return 0;
    ll cur=gcd(a,gcd(b,c));
    a/=cur,b/=cur,c/=cur;
    cur=(a*R+b)/c;
    ll sm=cur*n*(n+1)/2;
    b-=c*cur,cur=(a*R+b)/c*n;
    return sm+n*cur-getans(a*c,-b*c,a*a*r-b*b,cur);
}

inline void work()
{
    read(n),read(r);
    R=sqrt(r);
    int rr=(int)R;
    if(rr*rr==r){write(rr&1?(n&1?-1:0):n);return;}
    write(n-2*getans(1,0,1,n)+4*getans(1,0,2,n));
}
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。