题解有空补，咕咕咕。

卡常科技：Binary Jacobi

前置知识：$\texttt{Binary gcd}$。

• 科技用于快速计算模大素数的二次剩余。经 EI 提示探索发现。

• long long 大素数下对比是快速幂直接做的 $1/3$，和 $\texttt{Binary gcd}$ 一样优化明显。

下文 $\left(\dfrac{p}{q}\right)$ 为 $\text{Jacobi}$ 符号。

原理（部分证明）参见这里。

令 $p$ 为正整数，$a,b$ 为与 $p$ 互素的整数，有结论：

• 乘法结合：$\left(\dfrac{a}{p}\right)\times \left(\dfrac{b}{p}\right)=\left(\dfrac{ab}{p}\right)$

• $\left(\dfrac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}$

• 二次互反律：当 $p,q$ 为奇数且 $(p,q)=1$ 时，$\left(\dfrac{p}{q}\right)\times \left(\dfrac{q}{p}\right)=(-1)^{\frac{(p-1)(q-1)}{4}}$

---

欲求 $\left(\dfrac{p}{q}\right)$，其中 $q$ 为奇数，$p$ 为与 $q$ 互素的任意数。

设 $p=2^mk$，则 $\left(\dfrac{p}{q}\right)=\left(\dfrac{2}{q}\right)^m\times \left(\dfrac{k}{q}\right)=(-1)^{\frac{m(q^2-1)}{8}}\times \left(\dfrac{k}{q}\right)$。

用二次互反律：$\left(\dfrac{p}{q}\right)=(-1)^{\frac{m(q^2-1)}{8}}\times(-1)^{\frac{(k-1)(q-1)}{4}}\times \left(\dfrac{q}{k}\right)$。

递归下去即可，复杂度类似 $\text{gcd}$ 的复杂度，为 $O(\log V)$，但是常数极小，快速幂 $30s$ 的这个 $4s^-$。

#define mytz __builtin_ctzll
inline bool jac(ull a,ull b)
{
	bool ans=0;
	while(1)
	{
		a%=b;if(a==1) return ans;
		short az=mytz(a),o=az&1&(((b*b-1)&15)!=0);a>>=az;
		ans^=o;if(a==1) return ans;
		ans^=((((a-1)*(b-1))&7)!=0);swap(a,b);
	}return ans;
}

本题做法同大众做法，只是把素数增大了保证正确性，实测没有这个优化你根本过不去。

本题代码实现。