前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >POJ 2891 中国剩余定理扩展 模版

POJ 2891 中国剩余定理扩展 模版

作者头像
用户2965768
发布2019-08-01 10:38:23
6360
发布2019-08-01 10:38:23
举报
文章被收录于专栏:wym

POJ 2891 扩展欧几里得 扩展中国剩余定理 两篇写的很好

x=a1∗x1+b1 x=a2∗x2+b2 a1,a2是模数,b1,b2是余数。 求x, 模数不互质。

代码语言:javascript
复制
#include<iostream>
using namespace std;
#define ll long long
const int maxn=1e5+5;
int n;
ll exgcd(ll a,ll b,ll &x,ll &y) {
	if(!b) {//解方程求 x,y a*x+b*y = gcd(a,b)
		x=1,y=0;
		return a;
	}
	ll re=exgcd(b,a%b,x,y),tmp=x;
	x=y,y=tmp-(a/b)*y;
	return re;
}
ll m[maxn],a[maxn];
ll work() {
	ll M=m[1],A=a[1],t,d,x,y;
	int i;
	for(i=2; i<=n; i++) {
		d=exgcd(M,m[i],x,y);//解方程
		if((a[i]-A)%d)return -1;//无解
		x*=(a[i]-A)/d,t=m[i]/d,x=(x%t+t)%t;//求x
		A=M*x+A,M=M/d*m[i],A%=M;//日常膜一膜 防爆
	}
	A=(A%M+M)%M;
	return A;
}
int main() {
    int i,j;
    while(scanf("%d",&n)!=EOF){
        for(i=1;i<=n;i++)scanf("%lld%lld",&m[i],&a[i]);// %m[i] 余 a[i]
        printf("%lld\n",work());
    }

	return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019年07月15日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档