BSGS的一道简单题，不过中间卡了一下没有及时取模，其他这里的100000007是素数，所以不用加上拓展就能做了。
代码如下：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <map> using namespace std; template<class T> T gcd(T a, T b) { return b ? a : gcd(b, a % b);}
typedef long long LL;
void gcd(LL a, LL b, LL &d, LL &x, LL &y) {
if (b) { gcd(b, a % b, d, y, x); y -= a / b * x;}
else d = a, x = , y = ;
}
const LL MOD = ;
const int N = ; LL multi(LL a, LL p) {
LL ret = ;
a %= MOD;
while (p > ) {
if (p & ) ret *= a, ret %= MOD;
a *= a, a %= MOD, p >>= ;
}
return ret;
}
map<LL, int> id;
vector<LL> rec[N];
LL mincol; void bs(LL b, LL x, LL rt) {
id.clear();
for (int i = ; i <= rt; i++) {
if (id.find(b) != id.end()) break;
id[b] = i;
b *= x, b %= MOD;
}
} LL gs(LL b, LL x, LL r) {
LL cur = b;
//for (int i = 0; i < 50; i++) {
//if (cur == r) return mincol + i + 1;
//cur *= x, cur %= MOD;
//}
int rt = (int) ceil(sqrt((double) MOD)) + ;
bs(b, x, rt);
LL st = multi(x, rt), p, q, d;
cur = ;
for (int i = ; i <= rt; i++) {
gcd(cur, MOD, d, p, q);
p %= MOD, p += MOD, p %= MOD, p *= r / d, p %= MOD;
if (id.find(p) != id.end()) return (LL) i * rt + id[p] + mincol + ;
cur *= st, cur %= MOD;
}
return -;
} LL bf(LL b, LL x, LL r) {
LL cur = b;
for (int i = ; i < MOD; i++) {
if (cur == r) return mincol + i + ;
cur *= x, cur %= MOD;
}
return -;
}
int main() {
//freopen("in", "r", stdin);
LL n, k, b, r, x, y, bres;
int T, cas = ;
cin >> T;
while (T-- && cin >> n >> k >> b >> r) {
for (int i = ; i < N; i++) rec[i].clear();
id.clear();
mincol = ;
for (int i = ; i < b; i++) {
cin >> x >> y;
if (id.find(y) == id.end()) id[y] = id.size() - ;
rec[id[y]].push_back(x);
mincol = max(mincol, x);
}
bres = ;
for (int i = , sz = id.size(); i < sz; i++) {
rec[i].push_back();
rec[i].push_back(mincol + );
sort(rec[i].begin(), rec[i].end());
for (int j = , szj = rec[i].size(); j < szj; j++) {
if (rec[i][j] - rec[i][j - ] - >= ) bres *= k * multi(k - , (LL) rec[i][j] - rec[i][j - ] - ) % MOD, bres %= MOD;
}
}
LL tmp = k * multi(k - , mincol - );
bres *= multi(tmp, n - id.size());
bres %= MOD;
cout << "Case " << cas++ << ": ";
if (bres == r) { cout << mincol << endl; continue; }
int cnt = ;
for (int i = , sz = id.size(); i < sz; i++) {
rec[i].pop_back();
if (rec[i][rec[i].size() - ] == mincol) bres *= k, bres %= MOD, cnt++;
}
bres *= multi(k - , n - cnt);
bres %= MOD;
k = multi(k - , n);
cout << gs(bres, k, r) << endl;
//cout << bf(bres, k, r) << endl;
}
return ;
}
——written by Lyon