【洛谷P2485】计算器

BSGS模板题
代码如下
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

LL fpow(LL a, LL b, LL c) {

  LL ret = 1 % c;

  for (; b; b >>= 1, a = a * a % c) {

    if (b & 1) {

      ret = ret * a % c;

    }

  }

  return ret;

}

LL bsgs(LL a, LL b, LL p) {

  b %= p;

  unordered_map<LL, LL> mp;

  LL t = (LL)sqrt(p) + 1;

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

    LL val = b * fpow(a, i, p) % p;

    mp[val] = i;

  }

  a = fpow(a, t, p);

  if (a == 0) return b == 0 ? 1 : -1;

  if (b == 0) return -1;

  if (b == 1) return 0;

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

    LL val = fpow(a, i, p);

    LL j = mp.find(val) == mp.end() ? -1 : mp[val];

    if (j >= 0 && i * t - j >= 0) {

      return i * t - j;

    }

  }

  return -1;

}

int main() {

  ios::sync_with_stdio(false);

  cin.tie(0), cout.tie(0);

  int T, opt;

  cin >> T >> opt;

  while (T--) {

    LL y, z, p;

    cin >> y >> z >> p;

    if (opt == 1) {

      cout << fpow(y, z, p) << endl;

    } else if (opt == 2) {

      if (y % p == 0) {

        cout << "Orz, I cannot find x!" << endl;

      } else {

        cout << z * fpow(y, p - 2, p) % p << endl;

      }

    } else {

      LL ret = bsgs(y, z, p);

      if (ret == -1) {

        cout << "Orz, I cannot find x!" << endl;

      } else {

        cout << ret << endl;

      }

    }

  }

  return 0;

}
巴特西

【洛谷P2485】计算器

最新文章

热门文章
