#175. 模立方根

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB 通过: 49 | 提交: 106

题目描述

这是一道模板题。

求关于 $x$ 的方程 $x^3 \equiv a \pmod p$ 的解。

第一行一个正整数 $T$ ，表示有 $T$ 组数据。

之后的 $T$ 行每行两个正整数 $a, p$ 。

每一组数据输出一行为方程的任意一个可行解，若无解则输出 $0$ 。

输入

3
16 19
114 998244353
514 131071

输出

0
504784271
0

$p$ 为奇素数，$T = 10^5, p < 2^{30}, a \in \mathbb{F}_p \setminus \{0\}$。