P1495 曹冲养猪

时间:2022-01-22 13:05:21

原题链接 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[],b[],s=,k=,m=,gbs=; //a数组存放猪圈数,b数组存放余猪,注意long long
cin>>n; for(int i=;i<=n;i++)
cin>>a[i]>>b[i]; for(int i=;i<=n;i++) //因为猪圈互质,所以最小公倍数直接用每个猪圈数之积
gbs*=a[i]; for(int i=;i<=n;i++)
if((a[i]==&&b[i]==)) //一步特判,如果猪圈数为1且无余猪,则说明只有1头猪 别说推不出来
{cout<<"";return ;}
for(int i=;i<=n;i++)
{
long long j=,k=;
for(int v=;v<=n;v++)
if(v!=i) k*=a[v]; //k为除了当前mod数本身其他mod数的积
while((k*j)%a[i]!=) //暴力搜解,求出k*j≡1 (mod a【i】)的解
j++;
s=(s+b[i]*k*j)%gbs; //中国剩余定理公式,每步mod一下,防止内存爆炸
} cout<<s%gbs;
return ;
}