uva 11916 Emoogle Grid （BSGS）-白红宇

uva 11916 Emoogle Grid （BSGS）

阅读量：5094 次

发布时间：2019-06-13

本文共 3003 字，大约阅读时间需要 10 分钟。

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

代码如下：

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
             8 9 using namespace std; 10 11 template
             
               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
              
                id; 30 vector
               
                 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 }