「DLESS-2」XOR and Number Theory

ID: 11628

Type: RemoteJudge

500ms

128MiB

Difficulty: 6

Uploaded By:

Tags>

O2优化

中国剩余定理 CRT

洛谷比赛

题目描述

给出 $n,m$ ，对于所有满足以下两个条件的二元组 $(x,y)$ ，求 $x^2\bmod(y^2-xy)$ 的和：

其中 $\oplus$ 表示按位异或运算。

由于结果可能很大，所以答案对 $10^9+7$ 取模。

本题有多组测试数据，第一行输入一个正整数 $T$ ，表示数据组数。

对于每组数据，输入一行两个数 $n,m$ 。

对于每组数据，输出一行一个数，代表答案。

3
8 3
11 3
114514 11451

7
13
184193935

对于所有数据，保证：

本题采用打包测试，各测试包描述如下：

Subtask	$n\le$	$\sum n\le$	$\sum m\le$	分值
$1$	$1000$			$10$
$2$	$10^4$
$3$	$10^7$		$10^5$
$4$	$5\times10^7$		$10^5$	$20$
$5$	$10^9$	$+\infty$	$1000$	$10$
$6$			$5000$
$7$			$3\times 10^4$
$8$			$10^5$	$20$