CodeForces Gym - 101620F Faulty Factorial(简单数论)

Posted on | In , ,

思路

分四种情况讨论，注意p保证是一个素数，这个条件非常关键。

  1. n>=2p，如果r!=0显然无解，因为p，2p已经有两个p因子了，所以模p余数只能为0，r==0则我们随便输出一个合法的即可
  2. n>p&&n<2p，r==0则随意变换一个除p外的数，不然暴力枚举。
  3. n==p，r==0则若n==2无解，否则随意输出一个合法解。如果r!=0那么因为p是素数，我们由威尔逊定理(p-1)!同余于p=1得到最后的判定条件为(p-1)i%p==r然后进行暴力枚举
  4. n<p，我们有1*2*…*n同余r（模p意义下），我们枚举i，对两边乘上1*2*…*n的逆元然后去掉i就是i位置该放的值，判定是否合法即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
#define ms(a,val) memset(a,val,sizeof(a))
#define ll long long
#define INF 0x7fffffff

using namespace std;

ll qpow(ll a,ll b,ll mod){
    ll ans=1ll;
    while(b){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod,b>>=1;
    }
    return ans%mod;
}

int main() {
    ll n,p,r;
    while(cin>>n>>p>>r){
        if(n==p){
            if(r==0){
                if(n==2)cout<<-1<<" "<<-1<<endl;
                else cout<<2<<" "<<1<<endl;
            }
            else{
                ll flag=0;
                for(int i=1;i<p;i++){
                    if(i*(p-1)%p==r){
                        cout<<p<<" "<<i<<endl;
                        flag=1;
                        break;
                    }
                }
                if(!flag)cout<<-1<<" "<<-1<<endl;
            }
        }
        else if(n>=2*p){
            if(r!=0)cout<<-1<<" "<<-1<<endl;
            else cout<<p+1<<" "<<1<<endl;
        }
        else if(n>p&&n<2*p){
            if(r==0)cout<<p+1<<" "<<1<<endl;
            else{
                ll ans=1,flag=0;
                for(ll i=2;i<=n;i++){
                    if(i!=p)ans=(ans*i)%p;
                }
                for(ll i=1;i<p;i++){
                    if((ans*i)%p==r){
                        cout<<p<<" "<<i<<endl;
                        flag=1;
                        break;
                    }
                }
                if(!flag)cout<<-1<<" "<<-1<<endl;
            }
        }
        else{
            ll ans=1,flag=0,pos=0,num=0;
            for(ll i=2;i<=n;i++)ans=(ans*i)%p;
            ans=qpow(ans,p-2,p);
            for(ll i=2;i<=n;i++){
                ll temp=r*i%p*ans%p;
                if(temp>=1&&temp<i){
                    cout<<i<<" "<<temp<<endl;
                    flag=1;
                    break;
                }
            }
            if(!flag)cout<<-1<<" "<<-1<<endl;
        }
    }
	return 0;
}