原题链接 https://www.luogu.org/problemnew/show/P1495
这个题明显的中国剩余定理（孙子定理），如果有不懂孙子定理的点这个链接https://baike.baidu.com/item/%E5%AD%99%E5%AD%90%E5%AE%9A%E7%90%86/2841597?fr=aladdin
如果不想看那么一大堆的字母也可以听我简单说一下（大佬勿喷）：
中国剩余定理是求一次同余方程组的，比如本题的输入样例可以写成如下同余方程组：
x≡1 （mod 3）
x≡1 （mod 5）
x≡2 （mod 7）
那么同时满足以上三个同余方程的最小解就是本题的答案。
先求mod的数3，5，7的最小公倍数gbs是3*5*7=105 并把最小公倍数gbs写成当前mod的数*其余mod的数的积 即105=3*（5*7）=3*35=5*（3*7）=5*21=7*（3*5）=7*15；
随后我们设辅助方程
35x≡1 （mod 3） 1式 这里35是除了3这个mod数，其余mod数的积，即5*7（也可以理解成最小公倍数gbs 105/3=35），还有余数一定要为1不要问为什么
21x≡1 ( mod 5 ) 2式
15x≡1 (mod 7 ) 3式
由1式得： x≡2 （mod 3）
由2式得： x≡1 （mod 5）
由3式得： x≡1 （mod 7）
那么此题的解x≡一开始由题意列出的第一个同余方程的余数*第一个辅助方程的余数*（最小公倍数gbs/当前mod数）+......+一直到最后一个同余方程
所以x≡1*2*35+1*1*21+2*1*15≡121≡16 （mod105）
现在给出AC代码
#include<iostream> #include<cstdio> using namespace std; int main() { long long n,a[11],b[11],s=0,k=1,m=0,gbs=1; //a数组存放猪圈数，b数组存放余猪，注意long long cin>>n; for(int i=1;i<=n;i++) cin>>a[i]>>b[i]; for(int i=1;i<=n;i++) //因为猪圈互质，所以最小公倍数直接用每个猪圈数之积 gbs*=a[i]; for(int i=1;i<=n;i++) if((a[i]==1&&b[i]==0)) //一步特判，如果猪圈数为1且无余猪，则说明只有1头猪 别说推不出来 {cout<<"1";return 0;} for(int i=1;i<=n;i++) { long long j=1,k=1; for(int v=1;v<=n;v++) if(v!=i) k*=a[v]; //k为除了当前mod数本身其他mod数的积 while((k*j)%a[i]!=1) //暴力搜解，求出k*j≡1 （mod a【i】）的解 j++; s=(s+b[i]*k*j)%gbs; //中国剩余定理公式，每步mod一下，防止内存爆炸 } cout<<s%gbs; return 0; }