原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ42.html
题解
首先我们把式子改写一下：
$$(-1)^{\lfloor a\rfloor} \\=1-2(\lfloor a\rfloor \bmod 2)\\=1-2(\lfloor a\rfloor -2\lfloor \frac a2 \rfloor)$$
于是问题就变成了求解：
$$f(a,b,c,n) = \sum_{i=1}^n \left\lfloor \frac {a\sqrt{r} +b}{c}i\right\rfloor$$
按照类欧几里得算法的思路，我们把他变成一个 二维坐标系中 数梯形内整点 的问题，通过不断翻转坐标系搞一搞。
首先求出 $\left\lfloor \frac {a\sqrt{r} +b}{c}\right\rfloor$ 的值，即梯形短的一个底边的长度下取整。
然后把梯形转化成一个三角形。
然后把坐标系按照直线 $y=x$ 翻转，那么斜率取倒数：
$$\frac c {a\sqrt{r} + b} = \frac{c(a\sqrt r -b)}{a^2r-b^2} = \frac {ac\sqrt r -bc}{a^2r-b^2}$$
然后像类欧一样递归下去就好了。
代码
#include <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof (x))
#define int long long
using namespace std;
typedef long long LL;
LL read(){
LL x=0,f=0;
char ch=getchar();
while (!isdigit(ch))
f|=ch=='-',ch=getchar();
while (isdigit(ch))
x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return f?-x:x;
}
int T,n,r;
double rt;
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
int f(int a,int b,int c,int n){
if (!n)
return 0;
int t=gcd(a,gcd(b,c));
a/=t,b/=t,c/=t;
double k=1.0*(rt*a+b)/c;
int kk=(int)k;
k-=kk;
int m=(int)(k*n);
b-=c*kk;
return n*m+kk*(n+1)*n/2-f(a*c,-b*c,a*a*r-b*b,m);
}
signed main(){
T=read();
while (T--){
n=read(),r=read();
rt=sqrt(r);
int t=(int)rt;
if (t*t==r){
if (r&1)
puts(n&1?"-1":"0");
else
printf("%lld\n",n);
}
else
printf("%lld\n",n-2*f(1,0,1,n)+4*f(1,0,2,n));
}
return 0;
}