UOJ Logo Universal Online Judge

UOJ

#42. 【清华集训2014】Sum

统计

给定正整数 $n, r$,求

\begin{equation} \sum_{d = 1}^{n}{(-1)^{\left\lfloor \sqrt{d~\times~r~\times~d} \right\rfloor}} \end{equation}

输入格式

第一行一个数 $T$,表示有 $T$ 组测试数据。

接下来 $T$ 行,每行两个正整数 $n, r$。

输出格式

输出 $T$ 行,每行一个整数表示答案。

样例一

input

3
3 5
3 6
3 7

output

3
1
-1

限制与约定

对于 30% 的数据,满足 $n \leq 10^5, r \leq 10^2, T \leq 10$;

对于 60% 的数据,满足 $n \leq 10^7, r \leq 10^3, T \leq 10^2$;

对于 100% 的数据,满足 $n \leq 10^9, r \leq 10^4, T \leq 10^4$。

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

来源

中国国家队清华集训2014~2015 Day 3 - By 罗雨屏

下载

样例数据下载