首页 > 代码库 > 求解一元线性同余方程组模版
求解一元线性同余方程组模版
解法:直接上模版。
扩展欧几里德的模版:
typedef long long LL; LL ex_gcd(LL a,LL b,LL &x,LL &y) { if(b==0) { x=1; y=0; return a; } LL d=ex_gcd(b,a%b,x,y); LL t=x; x=y; y=t-a/b*y; return d; }
求解一元线性同余方程组模版:
LL solve(LL n) { LL a1,r1,a2,r2; LL a,b,c,r,x,y; bool ifhave=true; scanf("%lld%lld",&a1,&r1); for(LL i=1;i<n;i++) { scanf("%lld%lld",&a2,&r2); if(ifhave) { a=a1,b=a2,c=r2-r1; r=ex_gcd(a,b,x,y); if(c%r) { ifhave=false; continue; } LL t=b/r; x=(x*(c/r)%t+t)%t; r1=a1*x+r1; a1=a1*(a2/r); } } if(!ifhave) return -1; else return r1; }
题目: poj 2891 Strange Way to Express Integers
代码:
#include <iostream> #include <cstdio> #include <cmath> using namespace std; typedef long long LL; LL ex_gcd(LL a,LL b,LL &x,LL &y) { if(b==0) { x=1; y=0; return a; } LL d=ex_gcd(b,a%b,x,y); LL t=x; x=y; y=t-a/b*y; return d; } LL solve(LL n) { LL a1,r1,a2,r2; LL a,b,c,r,x,y; bool ifhave=true; scanf("%lld%lld",&a1,&r1); for(LL i=1;i<n;i++) { scanf("%lld%lld",&a2,&r2); if(ifhave) { a=a1,b=a2,c=r2-r1; r=ex_gcd(a,b,x,y); if(c%r) { ifhave=false; continue; } LL t=b/r; x=(x*(c/r)%t+t)%t; r1=a1*x+r1; a1=a1*(a2/r); } } if(!ifhave) return -1; else return r1; } int main() { LL n; while(cin>>n) { cout<<solve(n)<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。