BZOJ2242 计算器

目录

• BZOJ2242 计算器
• 题解
• ｃｏｄｅ

BZOJ2242 计算器

题目传送门

题解

一道比较模板的题目，第一个操作暴力快速幂搞，第二个操作暴力\(Exgcd\)搞，第三个操作暴力\(BSGS\)搞。注意判无解的情况就行了。

ｃｏｄｅ

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
#define PAUSE printf("Press Enter key to continue..."); fgetc(stdin);
ll y,z,p;
std::map<ll,ll>Mp;
int T,k;
/*==================Define Area================*/
ll Powe(ll x,ll y,ll p) {
    ll res=1;
    while(y) {
        if(y&1) res*=x,res%=p;
        x*=x;x%=p;
        y>>=1;
    }
    return res;
}

void Exgcd(ll a,ll b,ll &x,ll &y) {
    if(!b) {
        x=1,y=0;
        return ;
    }
    Exgcd(b,a%b,x,y);
    ll t=x;x=y;y=t-a/b*y;
}

ll Gcd(ll x,ll y) {
    if(!y) return x;
    else return Gcd(y,x%y);
}

void Solve1(ll a,ll b,ll c) {
    ll ans=Powe(a,b,c);
    printf("%lld\n",ans);
    return ;
}

void Solve2(ll a,ll b,ll c) {
    c=-c;
    ll G=Gcd(a,c);
    if(b%G!=0) {
        puts("Orz, I cannot find x!");
        return ;
    }
    a/=G;b/=G;c/=G;
    ll x,y;
    Exgcd(a,c,x,y);
    x=x*b%c;
    while(x<0) x+=c;
    printf("%lld\n",x);
    return ;
}

void Solve3(ll a,ll b,ll c) {
    Mp.clear();
    if(!(a%c)) {
        puts("Orz, I cannot find x!");
        return ;
    }
    ll m=ceil(sqrt(c));
    ll t=b;
    for (int i=0;i<=m;i++) {
        Mp[t]=i;
        t=t*a%c;
    }
    ll s=Powe(a,m,c);t=s;
    for (int i=1;i<=m;i++) {
        ll v=Mp[t];
        if (v!=0) {
            printf("%lld\n",i*m-v);
            return;
        }
        t=t*s%c; 
    }
    puts("Orz, I cannot find x!");
}

int main() {
    read(T);read(k);
    while(T--) {
        ll a,b,c;
        read(a);read(b);read(c);
        if(k==1) Solve1(a,b,c);
        else if(k==2) Solve2(a,b,c);
        else Solve3(a,b,c);
    }
    return 0;
}
/*
3 1
2 1 3
2 2 3
2 3 3
*/
/*
3 2
2 1 3
2 2 3
2 3 3
*/

BZOJ2242 计算器

原文：https://www.cnblogs.com/Apocrypha/p/9435621.html