首页 > 代码库 > 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)); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。