给定n，质数p和一个目标余数r

你需要改变n的阶乘中的一个数字，使得其积模p余r。

感觉不能融会贯通

我以为是个EXGCD的神仙题

首先n看似很大，但是明显n并不是完全有用

时若余数不为0则无解

对于有：

这个明显是一个不定方程，算出最小解再判断和p的大小关系就好了

但是怎么办？

由于这个不超过1e7我认为直接枚举变的暴力EXGCD

但很明显这是不能A掉的（虽然开了3s）

这个时候思考BSGS（北上广深新一线算法）

我们有一个在同余方程移位的操作

等价于

如果线性预处理逆元这是O1查询的

那么就A了

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define LL long longLL n,p,r;LL Check(LL Id,LL sum,LL mod){	LL ret=1;	for(int i=1;i<=n;++i){		if(i==Id)ret=ret*sum%mod;		else ret=ret*i%mod;	}	return ret;}void Solve50(){	for(int i=2;i<=n;++i){		for(int j=1;j
         
          =2*p){ if(!r)cout<
          
           <<" "<<1; else cout<<-1<<" "<<-1; return; } F[0]=1; if(p>n){ LL x,y; if(!r){ cout<<-1<<" "<<-1<<'\n'; return ; } for(int i=1;i<=n;++i){ F[i]=F[i-1]*i%p; } EXGCD(x,y,F[n],p); LL Inv=(x+p)%p; for(int i=2;i<=n;++i){ LL tmp=Inv*i%p*r%p; if(tmp
           
            >n>>p>>r; if(n<=500){ Solve50(); } else{ Solve100(); } return 0;}