题解 | #异次元空间#

异次元空间

http://www.nowcoder.com/practice/a8c588fd95754779a03faffd695a9b8a

题目： 有n个异次元空间，第0天的晚上第i个异次元空间有a[i]个暗黑物质。每天可以增长d[i],当增长到了P时，会有P个暗黑物质产生反应而消失，直到剩余的暗黑物质少于P个。还可以选择让某个异空间停止增长或者继续增长。求最少多少天可以使得有至少m个异次元空间达到k

方法一：拓展欧几里得算法求逆元

首先，我们用res[i]表示存储每个异次元空间达到k的最少天数，则

$(a [i] + r e s [i] * d [i]) (a[i]+res[i]* d[i])%p$ = $k$ ，

即第i个异次元空间的初始值+经过i天后暗物质的变化量=k, 则

$r e s [i] * d [i] = (k - a [i]) * (m o d p)$

$res[i]=(k-a[i])* d[i]^{-1}* (modp)$

则问题转化为求d[i]的逆元,可以采用扩展欧几里得算法求逆元

$d[i]* d[i]^{-1}%mod$ = $1$

$d[i]* d[i]^{-1}=k* mod+1$

$d[i]* d[i]^{-1}-k* mod=1$

$d[i]* d[i]^{-1}-k* mod=gcd(d[i],mod)$ ;

这里的 $d [i]$ 看做x,mod看做b，则就是求 $a x + b y = g c d (a, b)$ 的一组接x,y; 要求出这个最大公因数gcd(a,b)，用辗转相除法：

int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}

当到达递归边界的时候，b==0，a=gcd(a,b) 这时可以观察出来这个式子的一个解： $a * 1 + b * 0 = g c d (a, b) ， x = 1, y = 0$ ，这时的a和b已经不是最开始的那个a和b了，所以我们如果想要求出解x和y，就要回到最开始的模样。下一个状态为 $b * x 1 + (a$ % $b) * y 1$ = $g c d$ ,我们需要找出这两个相邻状态的联系，

$a$ % $b = a - (a / b) * b$

则 $gcd=bx_{1}+((a-a/b)* b)* y_{1}$ = $bx_{1}+ay_{1}-(a/b)* b * y_{1}$ = $ay_{1}+b(x_{1}-(a/b* y_{1})$ ,于是 $x=y_{1}$ , $y=x_{1}-a/b * y_{1}$ ,

将求得的x调整为0到P-1之间即为d[i]的逆元，再由公式求res[i]的值即为存储每个异次元空间达到k的最少天数，最后对res进行排序,取第m小的数

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param m int整型 
     * @param P int整型 
     * @param a int整型vector 
     * @param d int整型vector 
     * @param k int整型 
     * @return int整型
     */
    int solve(int n, int m, int P, vector<int>& a, vector<int>& d, int k) {
        // write code here
        vector<int>res;//存储每个异次元空间达到k的最少天数
        for(int i=0;i<n;i++){
            if(a[i]==k)res.push_back(0);//已经等于k则已经符合
            else{
                long x=0,y=0;
                exgcd(d[i],P,x,y);//求d[i]的逆元，用扩展欧几里得算法求得一组x0,y0和gcd
                long temp=((k-a[i])*x%P+P)%P;//调整x0到0~P-1的范围中即可，由公式推导的出每个异次元空间达到k的最少天数
                res.push_back(temp);
            }
        }
        sort(res.begin(),res.end());
        return res[m-1];
    }
    void exgcd(int a,int b,long&x,long&y){
        if(!b){
            x=1;y=0;return ;
        }
        exgcd(b,a%b,y,x);
        y-=(a/b)*x;
    }
};

复杂度：

时间复杂度： $O (n l n n)$ ,用扩展欧几里得算法求逆元的时间复杂度为 $O (l n n)$
空间复杂度： $O (n)$ ,额外数组大小不超过n

方法二：费马小定理求逆元

在方法一中对题目进行了基本分析胡我们发现只需要求出d[i]的逆元，还可以用费马小定理求逆元，在模为素数P的情况下，有费马小定理 $a^{(p-1)}=1(mod p)$ 那么 $a^{(p-2)}=a^{-1}(mod p)$ 也就是说a的逆元为 $a^{(p-2)}$ ,可以用快速幂算法求出 $a^{(p-2}$

快速幂： 快速幂算法的核心思想就是每一步都把指数分成两半，而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小，而最后表示的结果却一直不会变。如果指数是奇数时，我们抽出了一个底数的一次方，假如计算 $9^{5}$ ，这个 $9^{1}$ 我们先单独移出来,剩下的 $9^{4}$ ,又能够在执行“缩指数”操作了，把指数缩小一半，底数执行平方操作 $9^{5}=81^{2}* 9^{1}$ ,把指数缩小一半，底数执行平方操作 $9^{5}=6561^{1}*9^{1} =6561∗ 9$

alt 此时，指数又变成了一个奇数1，按照上面对指数为奇数的操作方法，再抽出一个底数的一次方，这里即为 $6561^{1}$ ，这个 $6561^{1}$ 单独移出来，但是此时指数却变成了0，也就意味着我们无法再进行“缩指数”操作了。最后的结果是9* 6561，指数为奇数5时，此时底数为9。当指数为奇数1时，此时的底数为6561。因此最后求出的幂结果实际上就是在变化过程中所有当指数为奇数时底数的乘积。

求得逆元后，同理得出第m小的res[i]

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param m int整型 
     * @param P int整型 
     * @param a int整型vector 
     * @param d int整型vector 
     * @param k int整型 
     * @return int整型
     */
    int solve(int n, int m, int P, vector<int>& a, vector<int>& d, int k) {
        // write code here
        vector<int>res;//存储每个异次元空间达到k的最少天数
        for(int i=0;i<n;i++){
            if(a[i]==k)res.push_back(0);//已经等于k则已经符合
            else{
                long x=fastpower(d[i],P-2,P);//用快速幂求得d[i]的逆元
                long temp=((k-a[i])*x%P+P)%P;//调整x0到0~P-1的范围中即可，由公式推导的出每个异次元空间达到k的最少天数
                res.push_back(temp);
            }
        }
        sort(res.begin(),res.end());
        return res[m-1];
    }
    long fastpower(long base,long power,long mod){
        long res=1;
        while(power>0){
            if((power&1)==1)res=res*base%mod;
            power>>=1;
            base=base*base%mod;
        }
        return res;
    }
};

复杂度：