洛谷P1495：https://www.luogu.org/problemnew/show/P1495
思路
建立了a个猪圈 有b头猪没有去处 即x≡b(mod a) x即是ans
把所有的关系全部列出来 即可看出是简单的中国剩余定理模板了
代码
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
#define ll long long
ll a[11],b[
11],n,M=
1,ans=
0;
void exgcd(ll a,ll b,ll &d,ll &x,ll &
y)
{
if(b==
0)
{
d=
a;
x=
1;
y=
0;
}
else
{
exgcd(b,a%
b,d,x,y);
ll t=
x;
x=
y;
y=t-a/b*
y;
}
}
void intchina()
{
ll Mi,x,y,i,d;
for(i=
1;i<=n;i++
)
{
Mi=M/
a[i];
exgcd(Mi,a[i],d,x,y);//扩展欧几里德求ti
ans=((ans+Mi*x*b[i])%M+M)%
M;
}
cout<<
ans;
}
int main()
{
cin>>
n;
for(ll i=
1;i<=n;i++
)
{
cin>>a[i]>>
b[i];
M*=a[i];
//计算M
}
intchina();//中国剩余定理
}
View Code
转载于:https://www.cnblogs.com/BrokenString/p/9655212.html
相关资源：JAVA上百实例源码以及开源项目
