over 3 years ago

求满足 的最小的 .

这个就是个典型的问题 , 也就是我们今天所讨论的东西

我们首先看互质的情况

对于 对于模意义下的都存在的逆元

那么我们可以先处理出的值,如果这些值中已经出现了我们所要求的,那么就可以返回了.

考虑没有得到的情况:

我们发现 , 已经求出来了

所以

右边的我们可以直接得到

所以左边的值如果可以在哈希表中找得到 , 也即是我们找到了一组解

复杂度 O()

然后如果没有互质的条件 , 我们又该怎么做 ?

考虑到这样的一个等价转换

我们可以轻易发现这样的一个等价转换

而此时的 是互质的 , 剩下的部分我们可以通过不断的提出后 , 得到互质的

具体来说是这样的

其中 是上一次处理得到后的 , 则有

此时 我们就可以用Bs_Gs来计算了.

要注意把左边的一大串乘逆元到右边 , 而且答案要加上

还是贴下代码吧

inline long long pow(long long t,long long y,long long z)
{
    long long r = 1;
    for ( ; y; y >>= 1 , t = t * t % z) 
        if (y & 1) r = r * t % z;
    return r;
}

inline void ex_gcd(long long a, long long b, long long &x, long long &y) 
{
    if (!b) {x = 1, y = 0; return; }
    else { ex_gcd(b, a % b, y, x), y -= (a / b) * x; }
}

inline long long Inv(long long x, long long y)
{
    long long rx, ry;  ex_gcd(x, y, rx, ry);
    return rx = (rx + y) % y;
}

int Log2(int x) {  return (int)(log(x + 1) / log(2) + 1);   }

int Bs_Gs(int x, int y, int z) 
{
    for (int i = 0, end = Log2((int)z); i <= end; ++i) if (pow(x, i, z) == y) return i;
    int g = gcd(x, z), rd = 0, m = (int)sqrt(z) + 1;;
    long long d = 1;
    for ( ; g != 1; ) 
        {
            if (y % g) return -1;
            ++rd, y /= g, z /= g;
            d = d * x / g % z, g = gcd(x, z);   
        }
    
    H.clear();
    for (int i = 1; i <= m; ++i) 
        {
            long long dt = pow(x, i, z);    
            if (d * dt % z == y) return i + rd;
            H[dt] = i;
        }
    
    long long inv = Inv(pow(x, m, z), z), now = y * inv % z;
    d = Inv(d, z), now = now * d % z;
    for (int i = 1; i <= m; ++i) 
        {
            if (H[now]) return i * m + H[now] + rd;
            now = now * inv % z;
        }
    return -1;
}
← SGU 280 NOIP2014 总结 →
 
comments powered by Disqus