信息学奥林匹克数学竞赛

我退学吧

算法概述

二次剩余求的其实是要求求得的值。

信息学竞赛没有证明!!

判断是否存在二次剩余,需要用到欧拉准则:
因为欧拉定理是因为这里的是奇质数,因此,然后对进行开方操作,在虚数域中 如果等于则可以开方,如果等于显然不可以开方,所以这样子判断是否有二次剩余就好了。

if(quick_pow(n,(p-1)/2,p)==p-1)
    return puts("No solutin"),0;

算法流程

给出,我们首先取一个数,这个是随机取得。然后我们对进行开方操作,直到开不了方为止。即找到一个满足

while(true) {
    int a=rand();
    w=(a*a-n+p)%p;
    if(quick_pow(w,(p-1)/2,p)==p-1) break;
}

即使是随机找,也不会找很久,

定理1:

中有能使方程有解

,如果存在不同的数,使他们带入后可以有解,那么很显然满足,所以满足,因为不可能是的倍数,所以的倍数,那么这样的数有个。因此随机到一个需要的的期望是

然后我们需要建立一个类似复数域的东西。我们平常的数学中有,我们需要建立一个类似的域,因此定义,所以满足,像正常复数那样开一个结构体重载一下运算符就好了。注意要使

定义出这个复数域的作用是

然后需要证明一些东西。。。

定理2:

证明:

定理3:

证明:直接用二项式定理化简得 然后把右边的组合数写成阶乘的形式发现总是会出现的倍数,然后在同余的意义下,就化成了。即得证。

然后我们就可以操作一番了。





由于本人是个蒟蒻。所以会的只有这么多了。
贴一个大爷对于素数,奇素数的幂,2的幂,合数的讨论的博客

2 对 “二次剩余”的想法;

发表评论

电子邮件地址不会被公开。 必填项已用*标注