题解 P2485 【[SDOI2011]计算器】

· · 题解

前两问都不难，这个BSGS还是比较难的……

我从隔壁的模板题复制的代码，所以写的是ExBSGS，比较冗长，虽然泛用性会更高，但是这题没有P点用……

对于第一问，直接套快速幂就行，BSGS要用到，就顺手解决了

对于第二问，扩欧求解，套费马小定理，数论渣表示一脸懵

对于第三问，BSGS硬上就行……

代码比较丑，凑合着看吧……

主程序还是挺简洁的233

#include<bits/stdc++.h>
#define ll long long
using namespace std;
map <ll,ll> m;
ll QuickPow(ll x,ll y,ll p)
{
    ll sum=1;
    while(y)
    {
        if(y&1) sum=sum*x%p;
        x=x*x%p;
        y>>=1;
    }
    return sum%p;
}
ll Gcd(ll x,ll y)
{
    return !x ? y : Gcd(y%x,x);
}
ll ExGCD(ll a,ll b,ll &x,ll &y)
{
    if(!b)
    {
        x=1;
        y=0;
        return a;
    }
    ll g=ExGCD(b,a%b,x,y);
    ll t=x;
    x=y;
    y=t-y*(a/b);
    return g;
}
ll BSGS(ll a,ll b,ll p,ll d)
{
    m.clear();
    b%=p;
    ll t=sqrt(p)+1,now=b,sum=d;
    for(int i=1;i<=t;i++)
    {
        now=now*a%p;
        m[now]=i;
    }
    now=QuickPow(a,t,p);
    for(int i=1;i<=t;i++)
    {
        sum=sum*now%p;
        if(m.count(sum)) return t*i-m[sum];
    }
    return -1;
}
int ExBSGS(int a,int b,int p)
{
    if(p==1) return 0;
    a%=p;
    b%=p;
    if(b==1) return 0;
    if(a==0)
    {
        if(b==0) return 1;
        return -1;
    }
    ll sum=1,tot=0;
    for(ll i=Gcd(a,p);i!=1;i=Gcd(a,p))
    {
        if(b%i) return -1;
        b/=i;
        p/=i;
        sum=sum*(a/i)%p;
        tot++;
        if(b==sum) return tot;
    }
    a%=p;
    ll cnt=BSGS(a,b,p,sum);
    if(cnt==-1) return -1;
    else return cnt+tot;
}
void Solve1()
{
    ll a,b,p;
    scanf("%lld %lld %lld",&a,&b,&p);
    printf("%lld\n",QuickPow(a,b,p));
}
void Solve2()
{
    ll a,b,p,x,y;
    scanf("%lld %lld %lld",&a,&b,&p);
    ll gcd=ExGCD(a,p,x,y);
    if(!(b%gcd))
    {
        ll t=p/gcd;
        x=(((x*b)/gcd)%t+t)%t;
        printf("%lld\n",x);
    }
    else printf("Orz, I cannot find x!\n");
}
void Solve3()
{
    ll a,b,p;
    scanf("%lld %lld %lld",&a,&b,&p);
    ll ans=ExBSGS(a,b,p);
    if(ans==-1) printf("Orz, I cannot find x!\n");
    else printf("%lld\n",ans);
}
int main()
{
    int Time,opt;
    scanf("%d %d",&Time,&opt);
    while(Time--)
    {
        if(opt==1) Solve1();
        else if(opt==2) Solve2();
        else if(opt==3) Solve3();
    }
    return 0;
}