#P3817. Sum

    ID: 3019 传统题 1000ms 256MiB 尝试: 414 已通过: 175 难度: 9 上传者: 标签>CF2600省选/NOI-连分数类欧几里得算法向下取整与向上取整奇偶性分析

Sum

题目描述

给定整数 n,rn,r,求 $\sum_{d=1}^n(-1)^{\lfloor\sqrt{d\times r\times d}\rfloor}$。

输入格式

第一行一个整数 TT 表示数据组数。

接下来 TT 行,每行两个整数 n,rn,r 表示一组数据。

输出格式

共 TT 行,第 ii 行一个整数表示第 ii 组数据的答案。

3
3 5
3 6
3 7
3
1
-1

数据规模与约定

对于 100%100\% 的数据,1≤n≤1091\leq n\leq 10^9,1≤r≤1041\leq r\leq 10^4,1≤T≤1041\leq T\leq 10^4。

来源

20152015 年国家集训队测试。