• 清华集训2014sum
• 求$$∑_{i=1}^{n}(-1){⌊i√r⌋}$$
• 多组询问，\(n\leq 10^9,t\leq 10^4, r\leq 10^4\)。
• 吼题解啊
• 具体已经讲得很详细了（找了好久才找到的良心题解。）
• 首先看到向下取整的式子要会拆开。
• 然后套类欧几里德。
• 这里的类欧几里德比较简单，因为可以看作是\(y=kx\)的正比例的向下整点。
• 如果\(k>1\)，那么就相当与直接算上面的点，然后把直线砍到\(k\leq 1\)。
• 否则取反函数，相当于减小了\(n\)而增大了\(k\)。
• 这样每次一定会缩小一半的问题规模，复杂度是\(O(logn)\)的。

#include<bits/stdc++.h>

#define R register int

#define ll long long

#define db double

using namespace std;

int T;ll n,r,ans,t;db q;

int gi(){

    R x=0,k=1;char c=getchar();

    while(c!='-'&&(c<'0'||c>'9'))c=getchar();

    if(c=='-')k=-1,c=getchar();

    while(c<='9'&&c>='0')x=(x<<3)+(x<<1)+c-'0',c=getchar();

    return x*k;

}

ll Gcd(ll x,ll y){return y?Gcd(y,x%y):x;}

ll sol(ll a,ll b,ll c,ll n){

	if(n==1)return (a*q+b)/c;

	if(n==0)return 0;

	ll gcd=Gcd(a,Gcd(b,c));

	a/=gcd,b/=gcd,c/=gcd;

	ll k=(a*q+b)/c;

	if(k==0){

		ll m=((a*q+b)/c*n);

		return m*n-sol(a*c,-b*c,a*a*r-b*b,m);

	}

	else return k*(n*(n+1)/2)+sol(a,b-c*k,c,n);

}

void cheat(){

	if(!(t&1))printf("%lld\n",n);

	else if(n&1)puts("-1");

	else puts("0");

}

int main(){

	T=gi();

	while(T--){

		n=gi(),r=gi(),q=sqrt(r),t=q;

		if(t*t==r){cheat();continue;}

		ans=n+4ll*sol(1,0,2,n)-2ll*sol(1,0,1,n);

		printf("%lld\n",ans);

	}

	return 0;

}