【LOJ】#2531. 「CQOI2018」破解 D-H 协议

题解

BSGS直接解出a和b来即可
代码

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int, int>

#define pdi pair<db, int>

#define mp make_pair

#define pb push_back

#define enter putchar('\n')

#define space putchar(' ')

#define eps 1e-8

#define mo 974711

#define MAXN 1000005

//#define ivorysi

using namespace std;

typedef long long int64;

typedef double db;

template <class T>

void read(T &res) {

    res = 0;

    char c = getchar();

    T f = 1;

    while (c < '0' || c > '9') {

        if (c == '-') f = -1;

        c = getchar();

    }

    while (c >= '0' && c <= '9') {

        res = res * 10 + c - '0';

        c = getchar();

    }

    res *= f;

}

template <class T>

void out(T x) {

    if (x < 0) {

        x = -x;

        putchar('-');

    }

    if (x >= 10) {

        out(x / 10);

    }

    putchar('0' + x % 10);

}

int P, g, S;

int inc(int a, int b) { return a + b >= P ? a + b - P : a + b; }

int mul(int a, int b) { return 1LL * a * b % P; }

int fpow(int x, int64 c) {

    int res = 1, t = x;

    while (c) {

        if (c & 1) res = mul(res, t);

        t = mul(t, t);

        c >>= 1;

    }

    return res;

}

struct node {

    int x, p, next;

} E[100005];

int head[mo + 5], sumE;

void add(int x, int p) {

    int u = x % mo;

    E[++sumE].next = head[u];

    E[sumE].x = x;

    E[sumE].p = p;

    head[u] = sumE;

}

int Query(int x) {

    int u = x % mo;

    for (int i = head[u]; i; i = E[i].next) {

        if (E[i].x == x) return E[i].p;

    }

    return -1;

}

int64 BSGS(int A, int C) {

    sumE = 0;

    memset(head, 0, sizeof(head));

    int t = 1;

    for (int i = 0; i < S; ++i) {

        if (t == C) return i;

        add(mul(t, C), i);

        t = mul(t, A);

    }

    int h = t;

    for (int i = 1;; ++i) {

        int x = Query(h);

        if (x != -1) return 1LL * i * S - x;

        h = mul(h, t);

        if (i > P / S) break;

    }

}

void Solve() {

    int A, B;

    read(A);

    read(B);

    int64 a = BSGS(g, A), b = BSGS(g, B);

    out(fpow(g, a * b % (P - 1)));

    enter;

}

int main() {

#ifdef ivorysi

    freopen("f1.in", "r", stdin);

#endif

    read(g);

    read(P);

    S = sqrt(P);

    int T;

    read(T);

    while (T--) {

        Solve();

    }

    return 0;

}
巴特西

【LOJ】#2531. 「CQOI2018」破解 D-H 协议

题解

代码

最新文章

热门文章
