二次剩余
2021/5/4 18:27:28
本文主要是介绍二次剩余,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
二次剩余算法
解决的问题:
形如:求是否存在x满足 : x^2 = n (mod p)
https://www.luogu.com.cn/problem/P5491
模板:
ll n,p; ll w; struct num{ //负数 ll x,y; }; num mul(num a,num b,ll p){ num ans = {0,0}; ans.x = ((a.x*b.x%p+a.y*b.y%p*w%p)%p+p)%p; ans.y = ((a.x*b.y%p+a.y*b.x%p)%p+p)%p; return ans; } ll qpw(ll a,ll b,ll p){ ll ans=1; while(b){ if(b&1)ans=ans%p*a%p; a=a%p*a%p; b>>=1; } return ans%p; } ll qpwii(num a,ll b,ll p){ //复数的快速幂 num ans={1,0}; while(b){ if(b&1)ans=mul(ans,a,p); a=mul(a,a,p); b>>=1; } return ans.x%p; } ll solve(ll n,ll p){ //x^2 = n (mod p) n %= p; if(p == 2)return n; if(qpw(n,(p-1)/2,p) == p-1)return -1; ll a; while(1){ a = rand()%p; w=((a*a%p-n)%p+p)%p; if(qpw(w,(p-1)/2,p) == p-1)break; } num x = {a,1}; return qpwii(x,(p+1)/2,p); } void work() { scanf("%lld%lld",&n,&p); if(!n) { printf("0\n"); return ; } ll ans1 = solve(n,p),ans2; if(ans1 == -1)printf("Hola!\n"); else{ ans2 = p - ans1; if(ans1 > ans2)swap(ans1,ans2); if(ans1 == ans2)printf("%lld\n",ans1); else printf("%lld %lld\n",ans1,ans2); } }
这篇关于二次剩余的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)