题解 P5491 [模板] 二次剩余

在写这道题前,我们需要了解一个方程。

$$x^2 \equiv n \ (mod\ p)$$

NR and QR

若对于奇素数p和满足 $n \nmid p$ 的整数 $n$,该方程的 $x$ 有整数解,则我们称 $n$ 是关于模 $p$ 的二次剩余,记做 $QR$ 。而对于无整数解的称呼其为模 $p$ 的二次非剩余。记做 $NR$。

而当 $n \equiv 0\ (mod\ p)$的情况,也就是 $n \mid p$ ,这种情况下n既不是 $QR$ 也不是 $NR$ 。

QR与NR的乘法法则

对于 $QR$ 和 $NR$ ,我们有如下性质。

性质一:$QR \times QR=QR$

性质二:$QR \times NR=NR$

性质三:$NR \times NR=QR$

性质四:$NR \times QR=NR$

性质与 $1$ 和 $-1$ 之间的性质很像,所以我们可以设 $QR=1$,$NR=-1$。

因为篇幅有限,性质的证明请自行Google。或阅读 《数论概论》

legendre 符号

所以对于$QR$与$NR$,我们可以定义 $legendre$ 符号。

$$\Big(\frac{n}{p}\Big)=\begin{cases} 1& \text{n 是模p的二次剩余}\\ -1& \text{n 是模p的二次非剩余} \end{cases}$$

欧拉准则

$$\Big(\frac{n}{p}\Big)\equiv n^{\frac{p-1}{2}}\ (mod\ p)$$

Cipolla 算法

我们可以找到一个整数 $a$,使得 $\Big(\frac{a^2-n}{p}\Big)=-1$,定义 $w^2=a^2-n$

然后 $(a+w)^{\frac{p+1}{2}}$ 就是原方程的一个解,而因为另一个解是在模p意义下对称的,所以就为 $p-(a+w)^{\frac{p+1}{2}}$

具体证明自行Google.

实现代码

#include <cstdio>
#include <cstdlib>
#include <ctime>

struct complex {
    long long x, y;
};

long long w;

complex mul(complex a, complex b, long long p) {
    complex ans = {0, 0};
    ans.x = (((a.x * b.x) % p + (a.y * b.y) % p * w % p) % p + p) % p;
    ans.y = (((a.x * b.y) % p + (a.y * b.x) % p) % p + p) % p;
    return ans;
}

long long complexPow(complex a, long long b, long long p) {
    complex ans = {1, 0};
    for (; b; b >>= 1) {
        if (b & 1) ans = mul(ans, a, p);
        a = mul(a, a, p);
    }
    return ans.x % p;
}

long long mypow(long long a, long long b, long long p) {
    long long ans = 1;
    for (; b; b >>= 1) {
        if (b & 1)
            ans = (ans * a) % p;
        a = (a * a) % p;
    }
    return ans;
}

long long cipolla(long long n, long long p) {
    n %= p;
    if (p == 2) 
        return n;
    if (mypow(n, (p - 1) / 2, p) == p - 1) 
        return -1;
    long long a = 1;
    while (1) {
        a = rand() % p;
        w = ((a * a % p - n) % p + p) % p;
        if (mypow(w, (p - 1) / 2, p) == p - 1) 
            break;
    }
    complex x = {a, 1};
    return complexPow(x, (p + 1) / 2, p);
}

int main() {
    srand((unsigned)time(0));
    int t;
    long long n, p;
    scanf("%d", &t);
    while (t--) {
        scanf("%lld %lld", &n, &p);
        long long k1 = cipolla(n, p);
        if (k1 == -1) {
            printf("Hola!\n");
            continue;
        }
        long long k2 = p - k1;
        if (k1 > k2)
            k1 ^= k2 ^= k1 ^= k2;
        if (k1 == k2)
            printf("%lld\n", k1);
        else
            printf("%lld %lld\n", k1, k2);
    }
    return 0;
}
本文《题解 P5491 [模板] 二次剩余》由 RM Olive (rmolives@gmail.com) 发布,如有版权纠纷及其他问题可以与我取得联系进行解决。
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇