题解 P5172 【Sum】

首先，特判$\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}$)。 代码: ```cpp 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)); } ```