33OJ
登录 注册

#P17703. [ICPC 2019 Nanjing R] Observation

[ICPC 2019 Nanjing R] Observation

题目描述

作为天文学家,Alice 驾驶她的宇宙飞船去观察宇宙中的一个未知物体。在通常的理论模型中,由于该物体的大小显著小于观察距离,它可以被视为空间中的一个点。

以该物体为中心建立一个空间直角坐标系,一个可能的完美观察位置是位于整点处的位置。Alice 将观察距离等于 d∈Zd \in \mathbb{Z} 的完美观察位置的数量记为 fdf_d。

现在,给定一个允许的观察距离范围 [L,R][L, R]、一个测试系数 KK 以及一个大素数 PP,请你计算 $\Big(\sum\limits_{d=L}^{R} (f_d \text{ xor } K)\Big) \pmod{P}$ 以探索风险因子。

输入格式

第一行包含一个整数 TT (1≤T≤10)(1 \le T \le 10),表示测试数据的组数。

对于每组测试数据,仅有一行包含四个整数 L,R,KL, R, K 和 PP,意义如上所述,其中 0≤L≤R≤10130 \le L \le R \le 10^{13},0≤K≤10180 \le K \le 10^{18},素数 PP 满足 P≤3×1013P \le 3 \times 10^{13} 且 R−L+1≤106R - L + 1 \le 10^6。

输出格式

对于每组测试数据,输出一行一个整数,表示所求的风险因子。

2
1 1 0 11
1 1 1 11
6
7

提示

翻译由 DeepSeek V4 Pro 完成