扩展剩余定理

#include <iostream>
using namespace std;
const int N = 100 ;
typedef long long ll ;
ll m[N] , c[N] ;
ll exgcd(ll a , ll b , ll &x , ll &y)
{
	if(b == 0)
	 {
	 	x = 1 , y = 0 ;
	 	return a ;
	 }
	 ll t = exgcd(b , a % b , y , x) ;
	 y -= a / b * x ;
	 return t ;
}
ll inv(ll a , ll b)
{
	ll x , y ;
	ll t = exgcd(a , b , x , y) ;
	while(x < 0) x += b ;
	return x ; 
}
ll gcd(ll a , ll b)
{
	return b == 0 ? a : gcd(b , a % b) ;
}
void solve()
{
	ll k ;
	cin >> k ;
	for(int i = 1 ;i <= k ;i ++) scanf("%lld%lld" , &m[i] , &c[i]) ;
	bool flag = true ;
	for(int i = 2 ;i <= k ;i ++)
	{
		ll m1 = m[i - 1] , c1 = c[i - 1] , m2 = m[i] , c2 = c[i] ;
		ll d = gcd(m1 , m2) ;
		if((c2 - c1) % d) {	flag = 0 ;break ;	}
		m[i] = m1 * m2 / d ;
		c[i] = (inv(m1 / d , m2 / d) * (c2 - c1) / d ) % (m2 / d) * m1 + c1 ;
		c[i] = (c[i] % m[i] + m[i]) % m[i] ;
	}
	printf("%lld\n" ,flag ?  c[k] : -1 ) ;
}
int main()
{
	solve() ;
	return 0 ;
}
全部评论

相关推荐

菜鸡29号:根据已有信息能初步得出以下几点: 1、硕士排了大本和大专 2、要求会多语言要么是招人很挑剔要么就是干的活杂 3、给出校招薪资范围过于巨大,说明里面的薪资制度(包括涨薪)可能有大坑
点赞 评论 收藏
分享
落叶随风呀:学校不好就放两栏,专业能力往前移, 政治面貌不是党员不如不写,籍贯湖南衡阳,或者湖南,浅尝辄止 基本信息排版不够美观,没有对齐 简历上花里胡哨的东西去掉 项目我不评价,因为我能力有限,且对mcu了解不足 但是这份简历掌握的水平,你可以海投试试,工作没问题但是工资应该不会高,因为搞mcu的小公司多
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务