【BZOJ3817（Sum（类欧几里得））】传送门
题意：
给定正整数 n,r ，求:
∑d=1n(?1)?dr√?
题解：
有点像类欧几里得。
只需要知道：
∑d=1n?dr√?%2
又因为
?x?%2=?x???x2??2
那么问题转化为求
∑d=1n?dx?
显然这是一条从原点出发的直线，要求的是它的下半部分的整数点。
有一个结论是如果这条直线的斜率大于1，那么先减掉1的斜率并加上这个斜率带来的一个直角三角形的贡献，这个新得到的直线覆盖的整点即为原来直线还没有加上的点。
类似于欧几里得，现在我们得到了一个斜率小于1的直线，那么考虑翻转这个坐标系来枚举y轴，发现又变成了一个子问题，这样迭代只会进行O(logn) 次。
具体的实现由于精度问题，我写的 long double 类并不能通过，所以要用 long long 类做分子分母来表示，记现在直线的斜率为 ax+bc(<1) ，要延伸到长度为 n 的位置。
先计算出在 n 的时候直线可以覆盖的点数 t ,并把 n?t 加入贡献中，此时我们多加入了上半部分的三角形，再把这个直线翻转，长度变为 t ，斜率变为 cax+b=c(ax?b)a2r?b2 ，减去这部分的贡献即可，这部分可以递归实现，代码非常的短。
Fastio部分可以忽略掉
#include
typedef long long ll;
typedef long double db;
using namespace std;
const int R_LEN=(1<<18)|1;
struct Fast_io{
char ibuf[R_LEN],obuf[R_LEN],*s,*t,*wt;
int buf[50];
Fast_io(){s=ibuf,t=ibuf;
wt=obuf;
}
~Fast_io(){fwrite(obuf,1,wt-obuf,stdout);
}
inline void print(char c){
(wt==(obuf+R_LEN)) && (fwrite(obuf,1,R_LEN,stdout),wt=obuf);
*wt++=c;
}
template
inline void W(T x){
if(x<0){print('-');
x=-x;
}
if(!x){print('0');
return;
}
while(x){buf[++buf[0]]=x%10;
x/=10;
}
while(buf[0])print(buf[buf[0]--]+'0');
}
inline char getc(){
(s==t) && (t=(s=ibuf)+fread(ibuf,1,R_LEN,stdin));
return (s==t)?-1:*s++;
}
inline int rd(){
char ch=getc();
int i=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;
ch=getc();
}
while(isdigit(ch)){i=(i<<1)+(i<<3)+ch-'0';
ch=getc();
}
return i*f;
}
}io;
int T,n,r;
db R,mxlen;
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;
}
inline ll solve(ll a,ll b,ll c,ll len){
if(!len) return 0;
ll t=gcd(a,gcd(b,c));
a/=t;
b/=t;
c/=t;
t=(a*R+b)/c;
ll sum=(len*(len+1)>>1)*t;
b-=c*t;
t=(a*R+b)*len/c;
return sum+t*len-solve(a*c,-b*c,a*a*r-b*b,t);
}
int main(){
for(T=io.rd();
T;
T--){
n=io.rd(),r=io.rd();
R=sqrt(r);
int t=(int)(R+0.5);
if(t*t==r){io.W((t&1)?((n&1)?-1:0):n);
io.print('\n');
continue;
}
int odd_cnt=solve(1,0,1,n);
odd_cnt-=2*solve(1,0,2,n);
io.W(n-2*odd_cnt),io.print('\n');
}
} 
