NC567 题解 | #异次元空间#

题意分析

• 给我们一个数组，这个数组的每个数都有一个每天都会进行一个增长，假如增长了x天，那么x天后的值为。但是这个数会对一个进行取模运算。同时，我们可以决定在什么时候让这个数字停止增长和继续增长。问至少要多少天可以使得这个数组里面的数字至少有个数字都为。

思路分析

• 首先，我们根据题目的意思进行分析，我们可以知道为了使得最后的天数最小，如果这个数字还没有到达，那么我们就让它继续进行增长，否则就立刻停止这个数字的增长。我们先不分析一个数组的情况，我们先看一个数字的情况。假如这里有一个初始的数字为，这个数字每天都会增长，而且增长后得到的会对(是素数）进行取模运算，问最少多少天可以增长到。其实这就是一个数学问题了。

• 我们假设所需要的天数为x,那么就可以得到

  

  由于这个是一个素数。直接利用快速幂进行求解即可。当我们找到所有的天数的时候，取第小的数字即可。

• 注意事项，这里会爆，需要开。

写法一 快速幂

• 快速幂的写法有点类似于分治的写法，就是当我们要求一个很大很大的情况的时候，我们先求这个大的情况的一半，如果还是很大的话，我们继续求一半，知道可以求为止，然后，我们求到了比较小的时候，我们有可以反推到很大的情况。这样，就实现了我们求一个很大的情况了。这有点像分治和归并的思想。这和重要。

• 这里对数组的每个数字使用快速幂，遍历数组的时间复杂度为,快速幂的时间复杂度为，总的时间复杂度为.

• 开了一个向量来存储每个数字所需要的天数，空间复杂度为

• 代码如下

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整型
     */
    typedef long long ll;
    // 快速幂进行求解，记得开long long
    ll qp(ll a,ll b,ll mod){
        ll sum=1;
        while(b){
            if(b&1) sum=sum*a%mod;
            b>>=1;
            a=a*a%mod;
        }
        return sum;
    }
    int solve(int n, int m, int P, vector<int>& a, vector<int>& d, int k) {
        // write code here
        vector<int> c;
        for(int i=0;i<n;i++){
            // 对每个位置上面的数字用快速幂进行求解
            ll tmp=qp(d[i],P-2,P);
            // 存储到C数组里面
            c.push_back((tmp*(k-a[i])%P+P)%P);
        }
        // 记得排序，取第k小的数字
        sort(c.begin(),c.end());
        return c[m-1];
    }
};

写法二 扩展欧几里得

• 对于上面的求逆元的操作，其实还有一种方法是利用扩展欧几里得的写法进行求解。我们可以先利用扩展欧几里得算法求出,然后进行求解。

• 这里对数组的每个数字使用扩展欧几里得，遍历数组的时间复杂度为,扩展欧几里得的时间复杂度为，总的时间复杂度为.

• 开了一个向量来存储每个数字所需要的天数，空间复杂度为

• 代码如下

  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整型
     */
    typedef long long ll;
    // 扩展欧几里得进行求解，记得开long long
    void exgcd(ll a,ll b,ll &x,ll &y){
        if(b==0){
            x=1,y=0;
            return;
        }
  
        exgcd(b,a%b,y,x);
        y=y-a/b*x;
    }
    int solve(int n, int m, int P, vector<int>& a, vector<int>& d, int k) {
        // write code here
        vector<int> c;
        for(int i=0;i<n;i++){
            // 对每个位置上面的数字用扩展欧几里得进行求解
            ll x=0,y=0;
            exgcd(d[i],P,x,y);
            // 存储到C数组里面
            c.push_back((x*(k-a[i])%P+P)%P);
        }
        // 记得排序，取第k小的数字
        sort(c.begin(),c.end());
        return c[m-1];
    }
  };