题意
有若干对数据：ai , bi 代表n%ai=bi , 求n的最小数目，其中ai之间两两互质
思路
中国剩余定理模板题 对于n个互质的数mi，存在x使得任意n个正整数ai满足： x≡a1(mod m1) x≡a2(mod m2) x≡a3(mod m3) … x≡ai(mod mi)
方程组的解为：x=a1 M1 x1 + a2 M2 x2 + … + ai Mi xi (在模M下有唯一解)
其中： M=m1*m2…mi Mi=M/mi xi的值为：Mi xi ≡ 1 ( mod mi )的解xi，可用扩展欧几里得求出（即求解：Mi * xi + yi * mi = 1)
注意M是累乘的积，数据范围开LL
代码
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std
;
#define ll long long
ll m
[15],a
[15];
ll x
,y
,g
,n
;
void exgcd(ll a
,ll b
)
{
if(b
==0){
x
=1,y
=0,g
=a
;
return;
}
exgcd(b
,a
%b
);
ll t
=x
;
x
=y
;
y
=t
-a
/b
*y
;
}
void Intchina()
{
ll M
=1,Mi
,ans
=0;
for(int i
=0;i
<n
;i
++) M
*=m
[i
];
for(int i
=0;i
<n
;i
++){
Mi
=M
/m
[i
];
exgcd(Mi
,m
[i
]);
ans
=(ans
+Mi
*a
[i
]*x
)%M
;
}
printf("%lld\n",(ans
+M
)%M
);
return;
}
int main()
{
scanf("%lld",&n
);
for(int i
=0;i
<n
;i
++)
scanf("%lld%lld",&m
[i
],&a
[i
]);
Intchina();
return 0;
}
