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)amodp=a2p(p−1)modp=a2p(p−1)modϕ(p)modp=a2p−1modp
求出
a
p
−
1
2
m
o
d
p
a^{\frac{p-1}{2}}\mod p
a2p−1modp就可以了。
注意
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;
}