BZOJ2242 [SDOI2011]電腦（洛谷P2485）

費馬小定理 BSGS

BZOJ題目傳送門

洛谷題目傳送門

第一問快速幂

第二問移個項，得 x=z∗inv(y)(modp) x = z ∗ i n v ( y ) ( mod p ) 。因為 p p 為質數，由費馬小定理，inv(y)=yp−2(modp)inv(y)=yp−2(modp)，快速幂求解。

第三問裸的BSGS

代碼：

#include<map>
#include<cmath>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define F inline
using namespace std;
typedef long long LL;
LL t,k,x,y,p,a,b;
map <LL,LL> mp;
F char readc(){
    static char buf[],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,,,stdin);
    return l==r?EOF:*l++;
}
F LL _read(){
    int x=; char ch=readc();
    while (!isdigit(ch)) ch=readc();
    while (isdigit(ch)) x=(x<<)+(x<<)+(ch^),ch=readc();
    return x;
}
F void writec(int x){ if (x>) writec(x/); putchar(x%+); }
F void _write(int x){ writec(x),puts(""); }
F LL ksm(LL a,LL b,LL p){
    LL ans=;
    while (b){
        if (b&) ans=ans*a%p;
        a=a*a%p,b>>=;
    }
    return ans;
}
F void BSGS(LL a,LL b,LL p){
    if ((!a)&&(!b)) return (void)puts("1");
    LL c=ceil(sqrt(p)),x=; mp.clear(),mp[]=c+;
    for (int i=;i<c;i++){ x=x*a%p; if (!mp[x]) mp[x]=i; }
    for (LL i=,n=,tmp=ksm(a,p-c-,p),l;i<c;i++){
        l=mp[b*n%p];
        if (!l) { n=n*tmp%p; continue; }
        if (l==c+) l=;
        _write(i*c+l); return;
    }
    puts("Orz, I cannot find x!");
}
int main(){
    for (t=_read(),k=_read();t;t--){
        x=_read(),y=_read(),p=_read(),x%=p;
        if (k==) _write(ksm(x,y,p));
        else{
            if ((!x)&&y){ puts("Orz, I cannot find x!"); continue; }
            k==?_write(y%p*ksm(x,p-,p)%p):BSGS(x,y,p);
        }
    }
    return ;
}