目录

BZOJ2242 计算器

题解

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

ｃｏｄｅ

#include 
    
     using namespace std;typedef long long ll;bool Finish_read;template
     
      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
      
       inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}template
       
        inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}template
        
         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
         
          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 12 1 32 2 32 3 3*//*3 22 1 32 2 32 3 3*/