#P12863. 乘法逆元
乘法逆元
乘法逆元
Problem Description
对于一个素数 ,我们知道,对于任意正整数 ,存在唯一的正整数 使得 ,称为 的乘法逆元,记为 。 本题中,你需要计算 $\bigoplus \limits_{i=1}^{p-1} \left( \operatorname{inv} \left( i \right)+2^k \right) \left(i+4^k \right)$,其中 。 由于结果可能过大,你只需要输出答案对素数 求余的结果即可。
Input
本题有多组测试数据。 输入的第一行有一个正整数 (),表示数据组数。 接下来有 行,每行有一个正整数 (,保证 是素数),表示一个询问。
Output
对于每组数据输出一行,表示上述算式的答案除以 的余数。
Sample Input
1
3
Sample Output
23
Hint
。 对应 。 对应 。 这两个数的异或和是 。
Source
2025“钉耙编程”中国大学生算法设计暑期联赛(9)