题解P2485 [SDOI2011]计算器

· · 个人记录

题目传送门

这道题主要可以分解成三个小问题。

1.求 y^z\bmod p 的值

很明显的快速幂模板，不会请见这里。

算法思路：通过指数 z 的二进制分解，合并两个相同的项的积，以 O(log_2n) 的时间复杂度轻松完成幂运算。

当然，每一步进行取模运算也是可以的，依靠公式 mn\bmod p=(a\bmod p)(b\bmod p)\bmod p，每一次合并与积运算可以进行取模运算。（具体过程详见度娘）

很简单，代码如下：

int qmi(int y, int z, int p){
    int ans = 1;
    while(z > 0){
        if(z&1){
            ans = ans * y % p;
        }
        y = y * y % p;
        z>>=1;
    }
    return ans;
}
//既然是快速幂，快速的位运算当然少不了qwq

2.求方程 xy\equiv z\pmod p 的最小非负整数解 x

原式可以化成 yx+pb=z 的形式，接下来也是一道简单的 EXGCD 板子题，不会请见这里。

又由原式易知 \gcd(y,p)\mid yx+pb，所以如果 z\nmid \gcd(y,z)，则输出 Orz, I cannot find x!。

算法思路：与 GCD 相同，代特殊解 x_0,y_0 进标准方程 ax+by=\gcd(a,b) 即可。具体请搭配代码理解。

难度不大，不过转化这步是关键点。

扩欧函数代码如下：

int x = 0, y = 0;
void exgcd(int a, int b, int &x, int &y){
    if(b == 0){
        x = 1;
        y = 0;
        return;
    }
    exgcd(b, a % b, x, y);
    int z = x;
    x = y;
    y = z - y * (a / b);
}
//x即为所求值

3.求方程 y^x\equiv z\pmod p 的最小非负整数解 x

很明显的百度搜索谷歌搜索 BSGS 算法模板，不会请见这里

这里详细的说一下 BSGS。

首先，令 x=i\times m-j,m=\left\lceil\sqrt p\right\rceil。

即 a^{i\times m-j}\equiv b\pmod p。

移项可得 a^{i\times m}\equiv b\times a^j\pmod p。

接下来就是 BSGS 算法：

1.从 0-m 的范围枚举 j, 将b\times a^j存进 Hash表。

2.从 1-m 的范围枚举 i, 从 Hash表找第一个满足方程a^{i\times m}\equiv b\times a^j\pmod p

此时有解 x=i\times m-j。

当枚举无解时，返回-1，即输出 Orz, I cannot find x!

这一问是铸就这道题是蓝题的关键。

详细请看代码：

int bsgs(int y,int z,int p) {
    map<int,int> hash; 
    hash.clear();
    z%=p;
    int m = sqrt(p) + 1;
    for(int i = 0;i < m;i++){
        hash[(int)z * qmi(y,i,p) % p] = i;
    }
    a = qmi(y,m,p);
    if(!y) return z==0?1:-1;
    for(int i = 1;i <= m;i++){
       int val = qmi(y,i,p);
       int j = hash.find(val)==hash.end()?-1:hash[val];
       if(j >= 0 && i * m - j >= 0) return i * m - j;
    }
    return -1;
}

题解代码可以将上列代码整合，所以不必提供。（逃