余下1匹猪就没地方结合了,不过依然有1头猪没有地点失去

洛谷P1495 曹冲养猪

题材叙述

自从曹冲作定矣大象后,曹阿瞒就从头怀疑让儿关系些事业,于是叫他及中华养猪场养猪,但是曹冲满不欢呼雀跃,于是在工作中马马虎虎,有同不成曹阿瞒想清楚母猪的数量,于是曹冲想狠狠耍曹阿瞒同将。举个例子,假如暴发16峰母猪,即便打了3个猪圈,剩下1条猪就从不地方结合了。如若盖了5只猪圈,可是如故发生1峰猪没有地点失去,然后一旦盘了7个猪圈,还有2头尚未地点失去。你当作曹总的私人秘书理所当然要用规范之猪数报为曹总,你该怎么惩罚?

问题叙述

打曹冲作定矣大象后,曹孟德就开怀疑让男干些事业,于是派他顶中华养猪场养猪,但是曹冲满不欢,于是在工作中马马虎虎,有平等浅曹阿瞒想精通母猪的数,于是曹冲想狠狠耍曹孟德同管。举个例子,假设发生16峰母猪,假使盘了3个猪圈,剩下1匹猪就从不地点结合了。假诺盖了5只猪圈,不过还是爆发1峰猪没有地方失去,然后一旦盘了7个猪圈,还有2头一直不地方失去。你当作曹总的私人秘书理所当然要用规范之猪数报叫曹总,你该怎么惩罚?

输入输出格式

输入格式:

 

首先尽包含一个平头n (n <= 10) –
建立猪圈的次数,解下来n行,每行多个整数ai, bi( bi <= ai <= 1000),
表示建立了ai只猪圈,有bi头猪没有去处。你得假定ai,aj互质.

 

输出格式:

 

输出包含一个恰巧整数,即为曹冲至少养母猪的多少。

 

输入输出格式

输入格式:

第一履包含一个整数n (n <= 10) –
建立猪圈的次数,解下来n行,每行两单整数ai, bi( bi <= ai <= 1000),
表示建立了ai独猪圈,有bi头猪没有去处。你可假定ai,aj互质.

出口格式:

输出包含一个刚整数,即为曹冲至少养母猪的数额。

输入输出样例

输入样例#1:

3
3 1
5 1
7 2

输出样例#1:

16

华夏剩余定理的模版题。

 

输入输出样例

输入样例#1: 复制

3
3 1
5 1
7 2

出口样例#1: 复制

16

分析

分外彰着的是中华剩余定理,推荐一首讲话得挺好的篇章:传送门

为何中国剩余定理必须模数两少于交互质也?因为假诺无互质的言辞就不曾逆元了。

怎用中国剩余定精通是唯一的吗?因为当模意义下一个往往要没逆元,要么就光生一个逆元。

华剩余定理对于跟和方程组是起限量法的,假设模数多个别休肯定互质怎么收拾?可以行使有限零星统一的沉思,两独少于个破。暂且就受他扩大中国剩余定理吧。

代码

图片 1图片 2

#include<cstdio>
using namespace std;
typedef long long ll;
ll n,x,y,a[12],m[12];
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;
}
inline ll inv(ll a,ll b){
    exgcd(a,b,x,y);
    return (x%b+b)%b;
}
ll china(){
    ll M=1,res=0;
    for(int i=1;i<=n;++i) M*=m[i];
    for(int i=1;i<=n;++i){
        ll w=M/m[i];
        res=(res+inv(w,m[i])*w*a[i])%M;
    }
    return (res+M)%M;
}
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;++i) scanf("%lld%lld",&m[i],&a[i]);
    printf("%lld\n",china());
    return 0;
}    

华剩余定理

 

图片 3图片 4

#include<cstdio>
using namespace std;
typedef long long ll;
ll n,a1,m1,a2,m2,x,y,c,d;
void exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){d=a; x=1;y=0;return;}
    exgcd(b,a%b,y,x); y-=(a/b)*x;
}
int main(){
    scanf("%lld",&n);
    scanf("%lld%lld",&m1,&a1);
    for(int i=2;i<=n;++i){
        scanf("%lld%lld",&m2,&a2);
        ll c=a2-a1,a=m1,b=m2;
        exgcd(a,b,x,y);
        x=(x*(c/d)%(b/d)+(b/d))%(b/d);
        a1=m1*x+a1; m1=m1/d*m2;
    }
    printf("%lld",a1);
    return 0;
}

扩充中国剩余定理

 

相关文章