URAL 1132 二次剩余-阿里云开发者社区

URAL 1132 二次剩余

2013-10-02 1644

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介：

1132. Square Root

Time limit: 1.0 second
Memory limit: 64 MB

The number x is called a square root of a modulo n (root( a, n)) if x* x = a (mod n). Write the program to find the square root of number a by given modulo n.

Input

One number K in the first line is an amount of tests ( K ≤ 100000). Each next line represents separate test, which contains integers a and n (1 ≤ a, n ≤ 32767, n is prime, a and n are relatively prime).

Output

For each input test the program must evaluate all possible values root( a, n) in the range from 1 to n− 1 and output them in increasing order in one separate line using spaces. If there is no square root for current test, the program must print in separate line: ‘No root’.

Sample

input	output
5 4 17 3 7 2 7 14 31 10007 20011	2 15 No root 3 4 13 18 5382 14629

求x*x=a(mod n) 解x。利用勒让德符号。

题意：x^2=a(mod n)（gcd(a,n)=1,n为素数）（有解x升序输出，无解输出"No root"(不包含双引号)）。

在数论中，二次剩余的欧拉判别法（又称欧拉准则）是用来判定给定的整数是否是一个质数的二次剩余。

若 $p$ 是奇质数且 $p$ 不能整除 $d$ ，则：

$d$ 是模 $p$ 的二次剩余当且仅当：

$d^{ \frac{p-1}{2}} \equiv 1 \pmod{p}$

$d$ 是模 $p$ 的非二次剩余当且仅当：

$d^{ \frac{p-1}{2}} \equiv -1 \pmod{p}$

以勒让德符号表示，即为： $d^{ \frac{p-1}{2}} \equiv \left( \frac{d}{p}\right) \pmod{p}$

费马小定理是数论中的一个定理：假如a是一个整数，p是一个质数，那么 $a^p - a$ 是p的倍数，可以表示为

$a^p \equiv a \pmod{p}$

如果a不是p的倍数，这个定理也可以写成

$a^{p-1} \equiv 1 \pmod{p}$

当n不整除a,n为奇素数时，方程x^2=a(mod n)有解<==>a^((n-1)/2)=1(mod n)，此时a称之为n的二次剩余类。相反无解<==>a^((n-1)/2)=-1(或者用n-1表示)(mod n)（欧拉准则）,此时称a为n的非二次剩余类。

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

long long pow_mod(long long a,long long b,long long p)
{
    long long res=1;
    while(b>0)
    {
        if(b&1)res=(res*a)%p;
        a=(a*a)%p;
        b>>=1;
    }
    return res;
}

long long solve(long long a,long long p)
{
    long long q=p-1,s=0;
    while(q%2==0)
    {
        s++;
        q>>=1;
    }
    if(s==1)return pow_mod(a,(p+1)/4,p);
    long long z;
    while(1)
    {
        z = 1 + rand()%(p - 1);
        if(pow_mod(z, (p - 1)/2,p) != 1) break;
    }
    long long c = pow_mod(z, q , p);
    long long r = pow_mod(a, (q + 1)/2, p);
    long long t = pow_mod(a, q, p);
    long long m = s, b,i;
    while(1)
    {
        if(t%p==1)break;
        for(i=1; i<m; i++)if(pow_mod(t,1<<i,p)==1)break;
        b=pow_mod(c,1<<(m-i-1),p);
        r=(r*b)%p;
        c=(b*b)%p;
        t=(t*c)%p;
        m=i;
    }
    return r;
}

int main()
{
    long long a,p,i;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%I64d%I64d",&a,&p);
        if(p==2)
        {
            if(a%p==1)printf("1\n");
            else printf("No root\n");
            continue;
        }
        if(pow_mod(a, (p-1)/2,p) != 1)
        {
            puts("No root");
            continue;
        }
        i=solve(a,p);
        if(p-i==i)printf("%I64d\n",i);
        else printf("%I64d %I64d\n",min(i,p-i),max(i,p-i));
    }
    return 0;
}

URAL 1132 二次剩余