[egin{aligned}
sum_{d=1}^n(-1)^{lfloor dsqrt r
floor}=&sum_{d=1}^n(-1)^{lfloor dsqrt r
floor mod 2}\
=&sum_{d=1}^n1-2(lfloor dsqrt r
floor mod 2)\
=&n-sum_{d=1}^n2(lfloor dsqrt r
floor-2lfloorfrac{lfloor dsqrt r
floor}{2}
floor)\
=&n+4sum_{d=1}^nlfloorfrac{dsqrt r}{2}
floor-2sum_{d=1}^nlfloor dsqrt r
floor
end{aligned}
]
将问题一般化，记(x=sqrt r)，其实我们求的是
[sum_{i=1}^n lfloor frac{ax+b}{c} i
floor
]
我们再记(frac{ax+b}{c}=k)，最后就是求
[sum_{i=1}^n lfloor ki
floor
]
仿照类欧的思想分类讨论
（1）若(kgeq 1)
[egin{aligned}
sum_{i=1}^n lfloor ki
floor=&sum_{i=1}^nlfloor ki-lfloor k
floor i+lfloor k
floor i
floor\
=&sum_{i=1}^nlfloor ki-lfloor k
floor i
floor+frac{n(n+1)}{2}lfloor k
floor\
=&sum_{i=1}^n lfloor frac{ax+b-clfloor frac{ax+b}{c}
floor*i}{c}
floor+lfloor k
floor * frac{n(n+1)}{2}
end{aligned}
]
（2）若(k<1)，继续考虑其几何意义
[egin{aligned}
sum_{i=1}^n lfloor ki
floor=&sum_{i=1}^nsum_{j=1}^{lfloor k*n
floor} [k*i>j]\
=&sum_{i=1}^nsum_{j=1}^{lfloor k*n
floor} [i>frac{j}{k}]\
=&sum_{j=1}^{lfloor k*n
floor}sum_{i=1}^n [i>frac{j}{k}]\
=&sum_{j=1}^{lfloor k*n
floor}
(n-lfloor frac{j}{k}
floor)\
=&lfloor k*n
floor*n-sum_{j=1}^{lfloor k*n
floor}lfloor frac{j}{k}
floor
end{aligned}
]
注意到使用（2）的时候需要k是一个无理数，所以预处理(r)是奇数时需要特判，同时递归时需要分母有理化
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 998244353
#define eps 1e-8
ll n,r;
double x;
int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
return x*f;
}
ll gcd(ll x,ll y)
{
if ((!x) || (!y)) return x+y;
else return gcd(y,x%y);
}
ll solve(ll a,ll b,ll c,ll n)
{
if (!n) return 0;
if (n==1) return (a*x+b)/c;
ll g=gcd(gcd(a,b),c);
a/=g;b/=g;c/=g;
ll k=(a*x+b)/c;
if (k!=0)
{
return k*n*(n+1)/2+solve(a,b-c*k,c,n);
}
else
{
ll tmp=(a*x+b)/c*n;
return tmp*n-solve(a*c,-b*c,a*a*r-b*b,tmp);
}
}
int main()
{
int T=read();
while (T--)
{
n=read();r=read();
x=sqrt((double)r);ll tmp=(ll)x;
if (tmp*tmp==r)
{
if (tmp&1) printf("%lld
",n-2*((n+1)>>1));
else printf("%lld
",n);
}
else printf("%lld
",n-solve(1,0,1,n)*2+solve(1,0,2,n)*4);
}
return 0;
}