首页 > 代码库 > poj 1808 Quadratic Residues 【平方剩余】【数论】

poj 1808 Quadratic Residues 【平方剩余】【数论】

题目链接:http://poj.org/problem?id=1808

题目大意:给你T组数据,每组数据一个a一个n,判断 x^2  ≡  a ( mod  n ) 能否成立。成立则输出1否则输出-1。

一个简单的平方剩余,只用判断能否有解即可。

#include<stdio.h>
#define LL long long

LL pow_mod(LL a, LL n, LL mod) {
    LL res = 1;
    while(n) {
        if (n & 1) res = res * a % mod;
        n >>= 1;
        a = a * a % mod;
    }
    return res;
}

LL modsqr(LL a, LL n){
    LL b,k,i,x;
    a = (a % n + n) % n;
    if(pow_mod(a, (n-1) / 2, n) == 1){
        return 1;
    }
    return -1;
}

int main ()
{
    int T,cas=1;
    scanf("%d",&T);
    while(T--)
    {
        LL a,b;
        scanf("%I64d%I64d",&a,&b);
        printf("Scenario #%d:\n%I64d\n\n",cas++,modsqr(a,b));
    }
}