题意
给定两个正整数(a,P,(a<P))，其中(P)是一个奇素数。根据(a)可以生成一个排列(b_x=axpmod{P},(1le xle P-1))。询问排列(b)的逆序对个数的奇偶性。
分析
通过置换奇偶性的定义我们可以把这题等价为求与群((/P)^{ imes})同构的置换群(Sym(/P))中与(a)对应的置换(sigma_a)(即(egin{pmatrix}1&2&3&dots P-1\a&2a&3a&dots (P-1)aend{pmatrix}))的奇偶性。
定义满足(a^xequiv1pmod{P})的最小正整数(x)为(delta_P(a))，那么置换(sigma_a)可以表示为(frac{P-1}{delta_P(a)})个长度为(delta_P(a))的轮换。又因为一个轮换的奇偶性与轮换长度(-1)相等，所以要求的就是(frac{P-1}{delta_P(a)}(delta_P(a)-1)equivfrac{P-1}{delta_P(a)}pmod{2})的奇偶性。
我们把(P-1)表示为(2^kp)，把(delta_P(a))表示为(2^lq)，(frac{P-1}{delta_P(a)})为奇数当且仅当(l=k)。令(t=frac pq)，则若(delta_P(a)=2^lqmid t(2^{k-1}q)=2^{k-1}p=frac{P-1}2)则说明(l<=k-1)(即(frac{P-1}{delta_P(a)})为偶数)，反之(frac{P-1}{delta_P(a)})则为奇数。那么我们就可以通过判断(a^{frac{P-1}2}pmod P)是否等于(1)得到答案。
代码
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using lll=__int128;
ll mpow(ll a,ll x,ll P) {
ll ans=1;
for(;x;x>>=1,a=(lll)a*a%P)
if(x&1) ans=(lll)ans*a%P;
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin>>t;
while(t--) {
ll a,P,p;
cin>>a>>P;
ll ans=mpow(a,(P-1)/2,P);
cout<<"01"[ans!=1]<<"
";
}
return 0;
}