uva 11916 Emoogle Grid （BSGS）

ゞ浴缸里的玫瑰 2021-12-14 12:43 205阅读 0赞

[UVA 11916][]

BSGS的一道简单题，不过中间卡了一下没有及时取模，其他这里的100000007是素数，所以不用加上拓展就能做了。

代码如下：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <cstdio>
      2 #include <iostream>
      3 #include <algorithm>
      4 #include <cstring>
      5 #include <vector>
      6 #include <cmath>
      7 #include <map>
      8 
      9 using namespace std;
     10 
     11 template<class T> T gcd(T a, T b) { return b ? a : gcd(b, a % b);}
     12 typedef long long LL;
     13 void gcd(LL a, LL b, LL &d, LL &x, LL &y) {
     14     if (b) { gcd(b, a % b, d, y, x); y -= a / b * x;}
     15     else d = a, x = 1, y = 0;
     16 }
     17 const LL MOD = 100000007;
     18 const int N = 555;
     19 
     20 LL multi(LL a, LL p) {
     21     LL ret = 1;
     22     a %= MOD;
     23     while (p > 0) {
     24         if (p & 1) ret *= a, ret %= MOD;
     25         a *= a, a %= MOD, p >>= 1;
     26     }
     27     return ret;
     28 }
     29 map<LL, int> id;
     30 vector<LL> rec[N];
     31 LL mincol;
     32 
     33 void bs(LL b, LL x, LL rt) {
     34     id.clear();
     35     for (int i = 0; i <= rt; i++) {
     36         if (id.find(b) != id.end()) break;
     37         id[b] = i;
     38         b *= x, b %= MOD;
     39     }
     40 }
     41 
     42 LL gs(LL b, LL x, LL r) {
     43     LL cur = b;
     44     //for (int i = 0; i < 50; i++) {
     45         //if (cur == r) return mincol + i + 1;
     46         //cur *= x, cur %= MOD;
     47     //}
     48     int rt = (int) ceil(sqrt((double) MOD)) + 1;
     49     bs(b, x, rt);
     50     LL st = multi(x, rt), p, q, d;
     51     cur = 1;
     52     for (int i = 0; i <= rt; i++) {
     53         gcd(cur, MOD, d, p, q);
     54         p %= MOD, p += MOD, p %= MOD, p *= r / d, p %= MOD;
     55         if (id.find(p) != id.end()) return (LL) i * rt + id[p] + mincol + 1;
     56         cur *= st, cur %= MOD;
     57     }
     58     return -1;
     59 }
     60 
     61 LL bf(LL b, LL x, LL r) {
     62     LL cur = b;
     63     for (int i = 0; i < MOD; i++) {
     64         if (cur == r) return mincol + i + 1;
     65         cur *= x, cur %= MOD;
     66     }
     67     return -1;
     68 }
     69 int main() {
     70     //freopen("in", "r", stdin);
     71     LL n, k, b, r, x, y, bres;
     72     int T, cas = 1;
     73     cin >> T;
     74     while (T-- && cin >> n >> k >> b >> r) {
     75         for (int i = 0; i < N; i++) rec[i].clear();
     76         id.clear();
     77         mincol = 1;
     78         for (int i = 0; i < b; i++) {
     79             cin >> x >> y;
     80             if (id.find(y) == id.end()) id[y] = id.size() - 1;
     81             rec[id[y]].push_back(x);
     82             mincol = max(mincol, x);
     83         }
     84         bres = 1;
     85         for (int i = 0, sz = id.size(); i < sz; i++) {
     86             rec[i].push_back(0);
     87             rec[i].push_back(mincol + 1);
     88             sort(rec[i].begin(), rec[i].end());
     89             for (int j = 1, szj = rec[i].size(); j < szj; j++) {
     90                 if (rec[i][j] - rec[i][j - 1] - 2 >= 0) bres *= k * multi(k - 1, (LL) rec[i][j] - rec[i][j - 1] - 2) % MOD, bres %= MOD;
     91             }
     92         }
     93         LL tmp = k * multi(k - 1, mincol - 1);
     94         bres *= multi(tmp, n - id.size());
     95         bres %= MOD;
     96         cout << "Case " << cas++ << ": ";
     97         if (bres == r) { cout << mincol << endl; continue; }
     98         int cnt = 0;
     99         for (int i = 0, sz = id.size(); i < sz; i++) {
    100             rec[i].pop_back();
    101             if (rec[i][rec[i].size() - 1] == mincol) bres *= k, bres %= MOD, cnt++;
    102         }
    103         bres *= multi(k - 1, n - cnt);
    104         bres %= MOD;
    105         k = multi(k - 1, n);
    106         cout << gs(bres, k, r) << endl;
    107         //cout << bf(bres, k, r) << endl;
    108     }
    109     return 0;
    110 }

——written by Lyon

转载于:https://www.cnblogs.com/LyonLys/p/uva\_11916\_Lyon.html

[UVA 11916]: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3067
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211214/0967cb8332494d27be43f6b14d38c005.png