异次元空间

最优题解

这道题首先要解决：最少经过几天，一个异次元空间会存在恰好k个物质
相当于求满足的最小的x。利用扩展欧几里得解同余方程可得。
那么牛牛只要在那天把空间冻上就可以了。
现在可以考虑二分答案，检查是否有m个空间的x是大于等于mid的。
当然直接排序后取第m小也是可以的
时间复杂度
算出来的天数可以存储在原本的a数组中，不使用额外空间，所以空间复杂度

long long exgcd(long long a,long long b,long long& x,long long &y){
    if(b==0) {
        x=1;y=0;
        return a;
    }
    long long x1,y1;
    long long ans=exgcd(b,a%b,x1,y1);
    x=y1;
    y=x1-a/b*y1;
    return ans;
}
int solve(int n, int m, int P, vector<int> &a, vector<int> &d, int k){
    assert(a.size() == n);
    assert(d.size() == n);
    for(int i = 0; i < n; ++i){
        long long x, y;
        exgcd(d[i], P, x, y);
        x%=P; x = x*(k-a[i]+P)%P; x = (x+P)%P; a[i] = x;
    }
    int l = 0, r = P;
    int ans;
    while(l <= r){
        int mid = (r+l)/2;
        int cnt = 0;
        for(int i = 0; i < n; ++i) if(a[i] <= mid) cnt++;
        if(cnt < m) l = mid+1;
        else ans = mid, r = mid-1;
    }return ans;
}