首页 > 代码库 > POJ 1808 + Ural 1132 平方剩余
POJ 1808 + Ural 1132 平方剩余
链接:http://poj.org/problem?id=1808
http://acm.timus.ru/problem.aspx?space=1&num=1132
题意:两道题都是模板题,第一个是判断是否有平方剩余,第二个是计算平方剩余。
思路:平方剩余就是给定a,n(n为质数) 问 x^2 ≡ a (mod n) 是否有解,可以用a^((n - 1)/2) ≡ ±1(mod n) 当为1是二次剩余,为-1是非二次剩余。
资料:http://blog.csdn.net/acdreamers/article/details/10182281
参考资料中基本正确,注意区分好同余和相等的关系。
代码:
LL w; LL pow_mod(LL aa,LL ii,LL nn) { if(ii==0) return 1%nn; LL temp=pow_mod(aa,ii>>1,nn); temp=temp*temp%nn; if(ii&1) temp=temp*aa%nn; return temp; } struct comp { LL r,i; }; comp multi(comp a, comp b, LL m) { comp ans; ans.r = (a.r * b.r % m + a.i * b.i % m * w % m) % m; ans.i = (a.r * b.i % m + a.i * b.r% m) % m; return ans; } comp pow_mod(comp a, LL b,LL m) { comp ans; ans.r = 1; ans.i = 0; while(b) { if(b & 1) { ans = multi(ans, a, m); b--; } b >>= 1; a = multi(a, a, m); } return ans; } LL Legendre(LL a, LL p) { return pow_mod(a, (p-1)>>1, p); } LL Quadratic_residue(LL n,LL p) { if(p==2) return 1; if (Legendre(n, p) + 1 == p) return -1; LL a = -1, t; while(1) { a = rand() % p; t = a * a - n; w=(t%p+p)%p; if(Legendre(w, p) + 1 == p) break; } comp temp; temp.r=a; temp.i=1; comp ans; ans=pow_mod(temp,(p+1)>>1,p); return ans.r; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。