【題解】SDOI-2011電腦

Problem

Bzoj

CodeVS

洛谷

給定 y y , zz , p p ，求

(1)yz(modp)yz(modp)

(2) x∗y≡z(modp) x ∗ y ≡ z ( mod p ) 中 x x 的最小非負整數解

(3)yx≡z(modp)yx≡z(modp)中 x x 的最小非負整數解

Solution

(1)

快速幂求解

(2)

可以用擴充歐幾裡得定理求解，但蒟蒻懶，就想用費馬小定理（ap−1≡1(modp)ap−1≡1(modp)， p p 為質數）求逆元

ap−1≡1(modp)ap−1≡1(modp)， p p 為質數

可得

a∗ap−2≡1(modp)a∗ap−2≡1(modp)， p p 為質數

是以

aa的逆元 a−1=ap−2 a − 1 = a p − 2

但本小題中同餘号右邊不是 1 1 ，不能直接使用費馬小定理求逆元，是以想法把右邊化為11：

x∗y≡z(modp) x ∗ y ≡ z ( mod p )

⇔ ⇔

x∗y∗z−1≡z∗z−1(modp) x ∗ y ∗ z − 1 ≡ z ∗ z − 1 ( mod p )

⇔ ⇔

x∗y∗z−1≡1(modp) x ∗ y ∗ z − 1 ≡ 1 ( mod p )

因為 x x 與y∗z−1y∗z−1互為逆元

是以 x=(y∗z−1)−1 x = ( y ∗ z − 1 ) − 1

其中 a a 的逆元a−1=ap−2a−1=ap−2

是以 x=(y∗zp−2)p−2 x = ( y ∗ z p − 2 ) p − 2

(3)

BSGS，具體就像分塊，可以在 O(p‾√) O ( p ) 内求解 yx≡z(modp) y x ≡ z ( mod p )

因為 y0≡1(modp) y 0 ≡ 1 ( mod p ) 且 yp−1≡1(modp) y p − 1 ≡ 1 ( mod p ) ，是以隻用考慮 x∈[1,p−1] x ∈ [ 1 , p − 1 ] 即可

用分塊思想，設 m=p‾√ m = p

然後可以預處理出 yi,i∈[0,m] y i , i ∈ [ 0 , m ]

接着從 z z 依次除以ymym，為了友善mod運算，乘以逆元 (ym)−1=yp−m−1 ( y m ) − 1 = y p − m − 1 （同樣由費馬小定理得出）

一旦遇到 yi,i∈[0,p‾√] y i , i ∈ [ 0 , p ] ，則答案ans=下降(除以 ym y m )的次數× m m +ii

擴充BSGS的筆記還沒寫，以後也許會補上筆記

Code

三道小題之間還是分得很清楚的

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rg register

template <typename _Tp> inline void read(_Tp&x){
    rg char c11=getchar(),ob=;x=;
    while(c11!='-'&&!isdigit(c11))c11=getchar();if(c11=='-')c11=getchar(),ob=;
    while(isdigit(c11))x=x*+c11-'0',c11=getchar();if(ob)x=-x;return ;
}

inline ll qpow(ll A,ll B,ll mod){
    ll ans=;
    while(B){
        if(B&)ans=ans*A%mod;
        A=A*A%mod;
        B>>=;
    }
    return ans;
}

int main(){
    rg int T,opt;
    read(T);read(opt);
    if(opt==){
        rg ll x,y,z;
        while(T--){
            read(x),read(y),read(z);
            printf("%lld\n",qpow(x,y,z));
        }
        return ;
    }
    if(opt==){
        rg ll y,z,p;
        while(T--){
            read(y),read(z),read(p);
            if(z%p==)puts("0");
            else if(z%p&&y%p==)puts("Orz, I cannot find x!");
            else printf("%lld\n",qpow(y,p-,p)*qpow(z,(p-)*(p-),p)%p);
        }
        return ;
    }
    if(opt==){
        map <ll,ll> mp;
        rg ll a,b,p;
        while(T--){
            read(a),read(b),read(p);
            if(p==&&b){puts("Orz, I cannot find x!");continue;}
            if(b==&&!a){puts("Orz, I cannot find x!");continue;}
            if(a%p==&&b){puts("Orz, I cannot find x!");continue;}
            a%=p,b%=p;
            mp.clear();
            ll m,v,base=;
            m=ceil(sqrt(p+));
            v=qpow(a,p-m-,p);
            mp[]=m;
            for(rg int i=;i<m;++i)if(!mp[base=base*a%p])mp[base]=i;
            for(rg int i=;i<m;++i){
                if(mp[b]){printf("%lld\n",i*m+(mp[b]==m?:mp[b]));goto con;}
                b=b*v%p;
            }
            puts("Orz, I cannot find x!");
            con: ;
        }
        return ;
    }
    puts("FCK");
    return ;
}