I love permutation

题意：

给一个正整数 a a a和一个奇质数 p ( a < p ) p(a<p) p(a<p)。令数组 b [ 1 ⋯ p − 1 ] b[1\cdots p-1] b[1⋯p−1]的元素为 b i = a x m o d    p b_i=ax\mod p bi​=axmodp，求 b b b中逆序对的数列模 2 2 2的结果。

思路：

又一个定理，如果 a 1 , a 2 , ⋯   , a n a_1,a_2,\cdots,a_n a1​,a2​,⋯,an​模 p p p是一个完全剩余系，且 gcd ⁡ ( k , b ) = 1 \gcd(k,b)=1 gcd(k,b)=1，那么 k a 1 , k a 2 , ⋯   , k a n ka_1,ka_2,\cdots,ka_n ka1​,ka2​,⋯,kan​模 p p p也是一个完全剩余系。
证明也很好证明。
假设不是完全剩余系，那么肯定存在 k a i ≡ k a j ( m o d    p ) ka_i\equiv ka_j(\mod p) kai​≡kaj​(modp)。那么 k ( a i − a j ) ≡ 0 ( m o d    p ) k(a_i-a_j)\equiv 0(\mod p) k(ai​−aj​)≡0(modp)，又因为 gcd ⁡ ( k , p ) = 1 \gcd(k,p)=1 gcd(k,p)=1，所以 a i ≡ a j ( m o d    p ) a_i\equiv a_j(\mod p) ai​≡aj​(modp)。与原本的条件相悖，所以假设不成立。
由于是求逆序对数量模 2 2 2的值，就相当于求排列的奇偶性。
我们可以通过 ∏ 0 ≤ i < j < p b i − b j ∏ o ≤ i < j < p i − j \cfrac{\prod\limits_{0\le i\lt j\lt p} b_i-b_j}{\prod\limits_{o\le i\lt j\lt p}i-j} o≤i<j<p∏​i−j0≤i<j<p∏​bi​−bj​​的值来判断。因为 ∏ o ≤ i < j < p i − j > 0 , ∏ o ≤ i < j < p i − j = ∣ ∏ 0 ≤ i < j < p b i − b j ∣ \prod\limits_{o\le i\lt j\lt p}i-j>0,\prod\limits_{o\le i\lt j\lt p}i-j=|\prod\limits_{0\le i\lt j\lt p} b_i-b_j| o≤i<j<p∏​i−j>0,o≤i<j<p∏​i−j=∣0≤i<j<p∏​bi​−bj​∣。如果有奇数个逆序对，式子的值就为 − 1 -1 −1，否则为 1 1 1。
把式子化简一下：
∏ 0 ≤ i < j < p b i − b j ∏ o ≤ i < j < p i − j = ∏ 0 ≤ i < j < p b i − b j i − j = ∏ 0 ≤ i < j < p a i m o d    p − a j m o d    p i − j = ∏ 0 ≤ i < j < p ( i − j ) a i − j m o d    p = a p ( p − 1 ) 2 m o d    p = a p ( p − 1 ) 2 m o d    ϕ ( p ) m o d    p = a p − 1 2 m o d    p \begin{aligned}\cfrac{\prod\limits_{0\le i\lt j\lt p} b_i-b_j}{\prod\limits_{o\le i\lt j\lt p}i-j}&=\prod\limits_{0\le i\lt j\lt p}\cfrac{b_i-b_j}{i-j}\\&=\prod\limits_{0\le i\lt j\lt p}\cfrac{ai\mod p-aj \mod p}{i-j}\\&=\prod\limits_{0\le i\lt j\lt p}\cfrac{(i-j)a}{i-j}\mod p\\&=a^{\frac{p(p-1)}{2}}\mod p\\&=a^{\frac{p(p-1)}{2}\mod \phi(p)}\mod p\\&=a^{\frac{p-1}{2}}\mod p\end{aligned} o≤i<j<p∏​i−j0≤i<j<p∏​bi​−bj​​​=0≤i<j<p∏​i−jbi​−bj​​=0≤i<j<p∏​i−jaimodp−ajmodp​=0≤i<j<p∏​i−j(i−j)a​modp=a2p(p−1)​modp=a2p(p−1)​modϕ(p)modp=a2p−1​modp​
求出 a p − 1 2 m o d    p a^{\frac{p-1}{2}}\mod p a2p−1​modp就可以了。
注意 a , p a,p a,p的上界是 1 0 18 10^{18} 1018，所以用__int128避免溢出。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;

int qpow(__int128 a,__int128 b,__int128 p)
{
	__int128 ans=1;
	while(b)
	{
		if(b&1)
			ans=ans*a%p;
		a=a*a%p;
		b>>=1;
	}
	return ans;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
		int a,p;
		cin>>a>>p;
		int v=qpow(a,(p-1)/2,p);
		cout<<(v==1?0:1)<<endl;
	}
	return 0;
}