标签: 二次剩余

  • 洛谷5110 块速递推

    $$ \text{特征根}x_1=\frac{233}{2}+\frac{13\sqrt{337}}{2},x_2=-\frac{13\sqrt{337}}{2}+\frac{233}{2} \\ \text{通项}a_n=ax_{1}^{n}+bx_{2}^{n} \\ \text{联立方程}\begin{cases} 0=a+b\\ 1=x_1a+x_2b\\ \end{cases} \\ \text{解出}a=\frac{\sqrt{337}}{4381},b=-\frac{\sqrt{337}}{4381} \\ \text{根据欧拉准则,}\left( 337 \right) ^{\frac{p-1}{2}}=\text{1,故求解二次剩余}216284168^2\equiv 337\left( mod\,\,10^9+7 \right) \\ \text{故在模}10^9+\text{7意义下,}x_1=\text{905847205,}x_2=94153035 \\ a=766769301 \\ \text{故}a_n=766769301\left( 905847205^n-94153035^n \right) \\ \text{对于一次询问,令}x=km+p\left( m\text{为块大小} \right) \text{,则有}x_{1}^{km+p}=x_{1}^{km}\times x_{1}^{p},\text{其中}p<m \\ \text{按照大小为}m\text{分块即可。} \\ \\ $$

    #include <cstdio>
    #include <iostream>
    using int_t = long long int;
    using std::cin;
    using std::cout;
    using std::endl;
    
    namespace Mker {
    unsigned long long SA, SB, SC;
    void init() { scanf("%llu%llu%llu", &SA, &SB, &SC); }
    unsigned long long rand() {
        SA ^= SA << 32, SA ^= SA >> 13, SA ^= SA << 1;
        unsigned long long t = SA;
        SA = SB, SB = SC, SC ^= t ^ SA;
        return SC;
    }
    }  // namespace Mker
    const int_t mod = 1e9 + 7;
    const int_t phi = mod - 1;
    const int_t a = 766769301;
    const int_t x1 = 905847205;
    const int_t x2 = 94153035;
    const int_t BLOCK_SIZE = 65536;
    int T;
    int_t x1s[mod / BLOCK_SIZE + 1], x2s[mod / BLOCK_SIZE + 1];
    int_t x1b[BLOCK_SIZE], x2b[BLOCK_SIZE];
    int_t power(int_t base, int_t index) {
        int_t result = 1;
        while (index) {
            if (index & 1) result = result * base % mod;
            index >>= 1;
            base = base * base % mod;
        }
        return result;
    }
    int main() {
        cin >> T;
    
        x1s[0] = x2s[0] = 1;
        int_t prex1 = power(x1, BLOCK_SIZE);
        int_t prex2 = power(x2, BLOCK_SIZE);
        for (int_t i = 1; i <= mod / BLOCK_SIZE; i++) {
            x1s[i] = x1s[i - 1] * prex1 % mod;
            x2s[i] = x2s[i - 1] * prex2 % mod;
        }
        x1b[0] = x2b[0] = 1;
        for (int_t i = 1; i < BLOCK_SIZE; i++) {
            x1b[i] = x1b[i - 1] * x1 % mod;
            x2b[i] = x2b[i - 1] * x2 % mod;
        }
        int_t result = 0;
        Mker::init();
        while (T--) {
            // int_t curr = 0;
            int x = (unsigned long long int)Mker::rand() % phi;
            int_t curr = ((x1s[x >> 16] * x1b[x & ((1 << 16) - 1)] -
                           x2s[x >> 16] * x2b[x & ((1 << 16) - 1)]) %
                              mod +
                          mod) %
                         mod * a % mod;
            result ^= curr;
        }
        cout << result << endl;
        return 0;
    }

     

  • 二次剩余Tonelli-Shanks算法

    $$ \text{求}\sqrt{a}\left( mod\,\,p \right) ,\text{其中}p\text{是奇素数。} \\ \text{令}p-1=2^s\times t,\text{其中}t\text{是奇数。} \\ \text{如果}s=\text{1,且}a\text{是模}p\text{的二次剩余,那么}\sqrt{a}=\sqrt{a^{\frac{p-1}{2}}\times a}=\sqrt{a^t\times a}=a^{\frac{t+1}{2}},\text{又因为}t\text{为奇数,所以可以直接计算得到}\sqrt{a} \\ \text{对于}s>\text{1,设}x_{s-1}=a^{\frac{t+1}{2}} \\ a^{\frac{p-1}{2}}=a^{2^{s-1}\times t}=\left( a^{-1}\times \left( a^{\frac{t+1}{2}} \right) ^2 \right) ^{2^{s-1}}=\left( a^{-1}\times x_{s-1}^{2} \right) ^{2^{s-1}}=1\left( a\text{是模}p\text{意义下的二次剩余} \right) \\ \text{所以}a^{-1}\times x_{s-1}^{2}\text{是模}p\text{意义下的}2^{s-1}\text{次单位根。} \\ \text{我们的目标是计算出模}p\text{意义下的}2^0\text{单位根,即计算出}a^{-1}\times x_{0}^{2}=\text{1,在这个同时我们也可以计算出}x_0,\text{进而得到方程解。} \\ \text{设}e_k\text{为模}p\text{意义下的}2^k\text{次单位根,则有} \\ e_{s-1}=a^{-1}\times x_{s-1}^{2} \\ \text{假设现在我们知道了}e_{s-k}\text{和}x_{s-k}\text{,如果} \\ e_{s-k}^{\begin{array}{c} 2^{s-k-1}\\ \end{array}}\equiv 1\left( mod\,\,p \right) ,\text{那么}e_{s-k-1}=e_{s-k},x_{s-k-1}=x_{s-k} \\ \text{否则,如果}e_{s-k}^{\begin{array}{c} 2^{s-k-1}\\ \end{array}}\equiv -1\left( mod\,\,p \right) \\ \text{即}\left( a^{-1}\times x_{s-k}^{2} \right) ^{2^{s-k-1}}\equiv -\text{1,那么我们显然需要求一个数}q,\text{使得} \\ \left( a^{-1}\times \left( qx_{s-k} \right) ^2 \right) ^{2^{s-k-1}}\equiv 1 \\ \text{整理后得}q^{2^{s-k}}\equiv -1 \\ \text{寻找一个模}p\text{意义下的非二次剩余}b,\text{则有}b^{\frac{p-1}{2}}\equiv -1 \\ b^{2^{s-1}t}\equiv -1 \\ b^{2^{k-1}t2^{s-k}}\equiv -1 \\ \left( b^{2^{k-1}t} \right) ^{2^{s-k}}\equiv -\text{1,故}q=b^{2^{k-1}t} \\ \text{所以}x_{s-k-1}=x_{s-k}\times q \\ \text{一直递推到}x_0\text{即可。} \\ $$

    模数固定为998244353:

    int_t modSqrt(int_t a) {
        const int_t b = 3;
        //mod-1=2^s*t
        int_t s = 23, t = 119;
        int_t x = power(a, (t + 1) / 2);
        int_t e = power(a, t);
        int_t k = 1;
        while (k < s) {
            if (power(e, 1 << (s - k - 1)) != 1) {
                x = x * power(b, (1 << (k - 1)) * t) % mod;
            }
            e = power(a, -1) * x % mod * x % mod;
            k++;
        }
        return x;
    }