Luogu

分析

数论模板三合一?

  1. 快速幂板子。
  2. exgcd 板子。
  3. BSGS 板子。

然后注意要开 long long 。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

namespace fastpow { int a,b,mod;
    inline int qpow(int a,int b) { int c=1;
        for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
        return c;
    }
    inline void work() {
        a=read(),b=read(),mod=read();
        printf("%lld\n",qpow(a,b));
    }
}

namespace exgcd { int a,b,mod;
    inline int exgcd(int a,int b,int& x,int& y) {
        if (!b) { x=1,y=0; return a; }
        int d=exgcd(b,a%b,y,x); y-=a/b*x;
        return d;
    }
    inline void work() {
        a=read(),b=read(),mod=read();
        int x,y,d=exgcd(a,mod,x,y);
        if (b%d) { puts("Orz, I cannot find x!"); return; }
        x=x*b/d; x=(x%(mod/d)+(mod/d))%(mod/d);
        printf("%lld\n",x);
    }
}

namespace bsgs { int a,b,mod;
    inline int qpow(int a,int b) { int c=1;
        for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
        return c;
    }
    inline int bsgs(int a,int b) {
        unordered_map<int,int> hash; hash.clear();
        b%=mod; int t=sqrt(mod)+1;
        for (re int i=0,j=1;i<t;++i,j=1ll*j*a%mod) hash[1ll*b*j%mod]=i;
        a=qpow(a,t);
        if (!a) return (b==0)?1:-1;
        for (re int i=0,j=1;i<=t;++i,j=1ll*j*a%mod) {
            int k=hash.find(j)==hash.end()?-1:hash[j];
            if (k>=0&&i*t-k>=0) return i*t-k;
        }
        return -1;
    }
    inline void work() {
        a=read(),b=read(),mod=read();
        int ans=bsgs(a,b);
        if (ans==-1) puts("Orz, I cannot find x!");
        else printf("%lld\n",ans);
    }
}

signed main() {
    int T=read(),op=read();
    while (T--) {
        if (op==1) fastpow::work();
        if (op==2) exgcd::work();
        if (op==3) bsgs::work();
    }
    return 0;
}
最后修改:2019 年 09 月 27 日 01 : 54 PM