【题目】

传送门

题目描述：

一个正整数 $k$k，给出 $k$k 对一些质数取模的结果，求符合条件的最小的 $k$k。

例如，$k \% 2 = 1$k%2=1，$k \% 3 = 2$k%3=2，$k \% 5 = 3$k%5=3。符合条件的最小的 $k = 23$k=23。

输入格式：

第 $1$1 行：$1$1 个数 $n$n 表示后面输入的质数及模的数量。（$2 \le n \le 10$2≤n≤10）

第 $2$2 ~ $n + 1$n+1行，每行 $2$2 个数 $p$p 和 $m$m，中间用空格分隔，$p$p 是质数，$m$m 是 $k \% p$k%p 的结果。$(2 \le p \le 100, 0 \le k &lt; p)$(2≤p≤100,0≤k<p)

输出格式：

输出符合条件的最小的 $k$k。数据中所有 $k$k 均小于 $10^9$109。

样例数据：

输入
3
2 1
3 2
5 3

输出
23

【分析】

如题，这是一道 CRT 的模板题。

具体的做法就看我的这篇博客中国剩余定理。

【代码】

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
ll a[15],m[15],M[15];
void exgcd(ll a,ll b,ll &x,ll &y)
{
	if(!b)  {x=1,y=0;return;}
	exgcd(b,a%b,y,x),y-=a/b*x;
}
int main()
{
	int n,i;
	scanf("%d",&n);
	ll x,y,ans=0,num=1;
	for(i=1;i<=n;++i)
	  scanf("%lld%lld",&m[i],&a[i]),num*=m[i];
	for(i=1;i<=n;++i)
	{
		M[i]=num/m[i];
		exgcd(M[i],m[i],x,y);
		x=(x+m[i])%m[i];
		ans+=a[i]*M[i]*x;
	}
	printf("%lld",ans%num);
	return 0;
}