閱讀401 返回首頁    go 技術社區[雲棲]

URAL 1132 二次剩餘

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



最後更新：2017-04-03 15:22:09

  上一篇：go Core Data多線程環境下pendingChange引發的排序不對問題
  下一篇：go CF 203 div2 E. Wrong Floyd 圖論