给定数 \(p,m\)，\(p\) 是质数，求
\[\sum_{i=0}^{p-1}\binom{2i}{i}m^i\bmod p \]多测，\(T\le 10^4\)，\(1\le m<p\le 10^{14}\)。
忽略 \(p=2\) 的情况，对 \(\displaystyle\binom{2n}{n}\) 变形：
\[\begin{aligned} \binom{2n}{n} &= 2^n\cdot\frac{1\times 3\times 5\times \cdots\times (2n-1)}{n!}\\ &\equiv(-2)^n\cdot\frac{\prod_{i=1}^{n}(p+1-2i)}{n!}\\ &\equiv(-4)^n\cdot\frac{\prod_{i=0}^{n-1}(\frac{p-1}{2}-i)}{n!}\\ &\equiv(-4)^n\cdot\binom{\frac{p-1}{2}}{n} \end{aligned} \]原式即
\[\sum_{i=0}^{p-1}(-4m)^i\binom{\frac{p-1}{2}}{i} \]二项式定理
\[(1-4m)^{\frac{p-1}{2}} \]时间复杂度 \(O(T\log p)\)。
#include<bits/stdc++.h>
#define ll long long
#define N 2000010
using namespace std;
ll read(){
ll x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*w;
}
ll p,m;
ll mul(ll x,ll y){
return (__int128)x*y%p;
}
ll qpow(ll k,ll b){
ll ret=1;
while(b){
if(b&1)ret=mul(ret,k);
k=mul(k,k),b>>=1;
}
return ret;
}
void solve(){
p=read(),m=read();
if(p==2ll)return puts("1"),void();
ll t=((1ll-4ll*m)%p+p)%p;
printf("%lld\n",qpow(t,(p-1ll)/2));
}
int main(){
int T=read();
while(T--)solve();
return 0;
}