【2021 Multi-University 2 J】I love permutation 题解

题目大意

  给定一个 $a$ 和一个奇质数 $p$（$1 \le a<p$），令 $b_x=ax\bmod p,\ x=1,2,\cdots,p-1$，则 $b$ 序列形成一个 $1$ 到 $p-1$ 的排列，求这个排列的逆序对数量 $\bmod 2$。

  $p \le 10^{18}$
  多测，$T \le 10^5$
  1s

$$\\$$ $$\\$$ $$\\$$

题解

  排列 $b_1,\cdots,b_n$ 的逆序对数量的奇偶性用这个式子表示，奇数就得到 $-1$，偶数就得到 $1$：

$$sign=\frac{\prod_{1 \le j < i \le n}b_i-b_j}{\prod_{1\le j < i \le n}i-j}$$

  这是因为，分子的 $(b_j,b_i)$ 如果是正序对，那么会跟分母的 $b_i-b_j$ 约掉；如果是逆序对，那么跟分母约掉之后还会多出一个 $-1$。

  式子代入这题：

$$sign = \frac{\prod_{1 \le j < i <p}b_i-b_j}{\prod_{1\le j < i <p}i-j} \equiv \frac{\prod_{1 \le j < i <p}ai-aj}{\prod_{1\le j < i <p}i-j} \equiv a^{\frac{(p-1)(p-2)}{2}} \equiv \left(a^{\frac{p-1}{2}}\right)^{-1} \pmod p$$

  所以就只需判断 $a^{\frac{p-1}{2}}$ 是 $1$ 还是 $-1$。

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

typedef long long LL;

LL mul(LL a,LL b,LL n) {return(a*b-(LL)(a/(long double)n*b+1e-3)*n+n)%n;}

LL Pow(LL x,LL y,LL mo) {
	LL re=1;
	for(; y; y>>=1, x=mul(x,x,mo)) if (y&1) re=mul(re,x,mo);
	return re;
}

int main() {
	int T;
	scanf("%d",&T);
	while (T--) {
		LL a,p;
		scanf("%lld %lld",&a,&p);
		printf("%d\n",(Pow(a,(p-1)>>1,p)&1)^1);
	}
}