SGU140. Integer Sequences
2021/8/1 6:06:08
本文主要是介绍SGU140. Integer Sequences,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
https://codeforces.com/problemsets/acmsguru/problem/99999/140
n元同余方程的求解
对于任意二元我们可以替换成kgcd(a,b),不断迭代下去最后会变成ax=b(mod p)的情况,然后,再返回去求解,得到g,然后后面变成不等式求解,直接将y[i-1]*g即可,但是要最小整数解。过程当中不断的用p取模,这样可以保证结果不会很大。因为只要一个结果,通项公式为b/d的一个组合,小的约束小,大的约束大, 大的一定包含在小的里面,那么大的一定是其中的一个解,所以mod p,但这并不是最小解,而是一个整数解。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 ll ex_gcd(ll a,ll b,ll &x,ll &y) 5 { 6 if(!b){x=1,y=0;return a;} 7 ll d=ex_gcd(b,a%b,x,y); 8 ll tmp=x; 9 x=y;y=tmp-a/b*y; 10 return d; 11 } 12 const ll N=520; 13 ll n,m[N],p,b,x[N],y[N],ans[N]; 14 int main() 15 { 16 scanf("%lld%lld%lld",&n,&p,&b); 17 for(int i=1;i<=n;i++) scanf("%lld",&m[i]),m[i]%=p; 18 ll g=m[1];m[n+1]=p; 19 for(int i=1;i<=n;i++) g=ex_gcd(g,m[i+1],x[i],y[i]); 20 if(b%g) printf("NO\n"); 21 else 22 { 23 printf("YES\n"); 24 g=b/g,y[0]=1; 25 for(int i=n;i>=1;i--) 26 { 27 g=(g*x[i]%p+p)%p; 28 ans[i]=(g*y[i-1]%p+p)%p; 29 } 30 for(int i=1;i<=n;i++) printf("%lld%c",ans[i],(i==n?'\n':' ')); 31 } 32 return 0; 33 }
这篇关于SGU140. Integer Sequences的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain
- 2024-06-19EntBot.ai: AI Website Chatbot for Product Guides and Development Doc
- 2024-06-17zero-shot-learning-definition-examples-comparison
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享