标签： 二次剩余

$$ \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;
}

$$ \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;
}