P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪[洛谷]

题目描述

自从曹冲解决了称象的难题后，曹操便开始琢磨着让儿子做些正经事业，于是派他到中原的养猪场去养猪。然而曹冲对此满心不悦，做起事来也马马虎虎。有一次，曹操想知道猪圈里母猪的数量，曹冲便想借此机会好好戏弄父亲一番。举个例子，假如有 16 头母猪，若建 3 个猪圈，就会有 1 头猪无处安放；若建 5 个猪圈，仍有 1 头猪没有去处；若建 7 个猪圈，则还剩 2 头猪无处可去。作为曹总的私人秘书，你自然应当准确无误地将母猪的数量报告给曹总，那么你该如何解决这个问题呢？

输入格式

第一行包含一个整数 n —— 建立猪圈的次数，接下来 n 行，每行两个整数 a i,b i ，表示建立了 a i 个猪圈，有 b i头猪没有去处。你可以假定 a 1∼a n互质

输出格式

输出包含一个自然数，即为曹冲至少养母猪的数目。

输入输出样例

输入 #1

3
3 1
5 1
7 2

输出 #1

16

制作不易，点个赞吧

要不然

代码如下：

#include<bits/stdc++.h>
using namespace std;
struct p{
int a1,b1;
}a[11];
int dcx(int x,int y){
if(x%y==0) return y;
else return dcx(y,x%y);
}
int main(){
long long n,an;
long long s=1;
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i].a1>>a[i].b1;
}
an=a[1].b1;
for(int i=1;i<n;++i){
s=s*a[i].a1/dcx(s,a[i].a1);
while(an%a[i+1].a1!=a[i+1].b1){
an+=s;
}
}
cout<<an;
return 0;
}