【SDOI2011】计算器

刺骨的言语ヽ痛彻心扉 2023-06-05 08:51 1阅读 0赞

### Description ###

给定$y, z, p$，求$x=y^\{z\} \\mod p$或$xy\\equiv z \\pmod p$或$y^x\\equiv z\\pmod p$中x的值

### Solution ###

第一个式子我们可以直接用快速幂求解答案。时间复杂度$O(log\_\{2\}z)$

第二个式子我们可以变形为$xy+Yp=z$，然后用扩展欧几里得算法求出$xy+Yp=gcd(y,p)$的解，然后利用裴蜀定理判断是否有解即可。

第三个式子我们可以应用BSGS算法求解。[详细的解释在这里][Link 1]

### Code ###

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

1 #include <cstdio>
     2 #include <map>
     3 #include <cmath>
     4 using namespace std;
     5 typedef long long ll;
     6 ll qpow(ll a, ll b, ll p) {
     7     ll ret = 1;
     8     while (b) {
     9         if (b & 1) ret = (ret * a) % p;
    10         a = a * a % p;
    11         b >>= 1;
    12     }
    13     return ret % p;
    14 }
    15 ll exgcd(ll a, ll b, ll &x, ll &y) {
    16     if (!b) {
    17         x = 1, y = 0;
    18         return a;
    19     }
    20     ll gcd = exgcd(b, a % b, x, y);
    21     ll x2 = x, y2 = y;
    22     x = y2;
    23     y = x2 - (a / b) * y2;
    24     return gcd;
    25 }
    26 map <ll, ll> h;
    27 ll BSGS(ll a, ll b, ll p) {
    28     h.clear();
    29     b %= p;
    30     ll t = (ll)sqrt(p) + 1;
    31     for (register int j = 0; j < t; ++j) {
    32         ll val = (ll)b * qpow(a, j, p) % p;
    33         h[val] = j;
    34     }
    35     a = qpow(a, t, p);
    36     if (a == 0) return b == 0 ? 1 : -1;
    37     for (register int i = 0; i <= t; ++i) {
    38         ll val = qpow(a, i, p);
    39         ll j = h.find(val) == h.end() ? -1 : h[val];
    40         if (j >= 0 && i * t - j >= 0) return i * t - j;
    41     }
    42     return -1;
    43 }
    44 int n, k;
    45 int main() {
    46     ll y = 0, z = 0, p = 0;
    47     scanf("%d%d", &n, &k);
    48     if (k == 1) 
    49         while (n--) {
    50             scanf("%lld%lld%lld", &y, &z, &p);
    51             printf("%lld\n", qpow(y, z, p));
    52         }
    53     else if (k == 2) 
    54         while (n--) {
    55             scanf("%lld%lld%lld", &y, &z, &p);
    56             ll x = 0, yy = 0;
    57             ll ret = exgcd(y, p, x, yy);
    58             if (z % ret != 0) {puts("Orz, I cannot find x!"); continue ;}
    59             ll now = p / ret;
    60             while (x < 0) x += now;
    61             printf("%lld\n", (x * (z / ret) % now) + now % now);
    62         }
    63     else 
    64         while (n--) {
    65             scanf("%lld%lld%lld", &y, &z, &p);
    66             ll ret = BSGS(y, z, p);
    67             if (ret == -1) puts("Orz, I cannot find x!");
    68             else printf("%lld\n", ret);
    69         }
    70     return 0;
    71 }

AC Code

转载于:https://www.cnblogs.com/shl-blog/p/11332183.html

[Link 1]: https://www.cnblogs.com/shl-blog/p/11295423.html
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/263f5c28263b46a0855e75d6114bda8f.png