BZOJ 2242: [SDOI2011]计算器 [快速幂 BSGS]-白红宇

BZOJ 2242: [SDOI2011]计算器 [快速幂 BSGS]

阅读量：5776 次

发布时间：2019-06-18

本文共 784 字，大约阅读时间需要 2 分钟。

题意：求\(a^b \mod p,\ ax \equiv b \mod p,\ a^x \equiv b \mod p\)，p是质数

这种裸题我竟然WA了好多次

第三个注意判断a和b整除p的情况

#pragma GCC optimize ("O2")#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         using namespace std;typedef long long ll;#define fir first#define sec secondinline int read() { char c=getchar(); int x=0, f=1; while(c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();} while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();} return x*f;}int a, b, p;ll Pow(ll a, int b, int p) { a%=p; ll ans=1; for(; b; b>>=1, a=a*a%p) if(b&1) ans=ans*a%p; return ans;}ll inv(int a, int p) { if(a%p==0) return -1; return Pow(a, p-2, p);}map
          
            ma;ll ind(int a, int b, int p) { a%=p; b%=p; ma.clear(); ll e=1; int m=sqrt(p)+0.5; for(int i=0; i