Vijos——T 1164曹冲养猪
2024-08-30 20:30:15
https://vijos.org/p/1164
描述
自从曹冲搞定了大象以后,曹操就开始捉摸让儿子干些事业,于是派他到中原养猪场养猪,可是曹冲满不高兴,于是在工作中马马虎虎,有一次曹操想知道母猪的数量,于是曹冲想狠狠耍曹操一把。举个例子,假如有16头母猪,如果建了3个猪圈,剩下1头猪就没有地方安家了。如果建造了5个猪圈,但是仍然有1头猪没有地方去,然后如果建造了7个猪圈,还有2头没有地方去。你作为曹总的私人秘书理所当然要将准确的猪数报给曹总,你该怎么办?
格式
输入格式
第一行包含一个整数n (n <= 10) – 建立猪圈的次数,解下来n行,每行两个整数ai, bi( bi <= ai <= 1000), 表示建立了ai个猪圈,有bi头猪没有去处。
//你可以假定ai,aj互质.
输出格式
输出包含一个正整数,即为曹冲至少养母猪的数目。
样例1
样例输入1
3
3 1
5 1
7 2
样例输出1
16
限制
来源
huyichen
裸CRT
#include <algorithm>
#include <cstdio> using namespace std; #define LL long long
LL n,a[],b[]; void exgcd(LL a,LL b,LL &x,LL &y)
{
if(!b) { x=; y=; return ; }
exgcd(b,a%b,x,y);
LL tmp=x; x=y;
y=tmp-a/b*y;
}
LL CRT()
{
LL ret=,tot=;
for(int i=;i<=n;i++) tot*=a[i];
for(int i=;i<=n;i++)
{
LL t=tot/a[i],x,y;
exgcd(t,a[i],x,y);
ret=(ret+x*b[i]*t)%tot;
}
return ret>=?ret:(ret+tot);
} int main()
{
scanf("%lld",&n);
for(int i=;i<=n;i++)
scanf("%lld%lld",a+i,b+i);
printf("%lld",CRT());
return ;
}
最新文章
- javascript动画系列第二篇——磁性吸附
- sed的应用
- JSP 运行
- svn merge和branch
- user-agent中的mozilla
- 40个Java集合面试问题和答案【下】【转载】
- 普通的101键盘在Mac上的键位对应
- Apache Pig处理数据示例
- PHPCMSV9上线方法及文件权限设置
- 读懂javascript深拷贝与浅拷贝
- 个人怎么申请微信小程序
- javascript 变量的引入、变量的声明、变量的初始化
- Arrlist的重要方法重写
- Firebird Embedded 部署的一个坑
- .net core实践系列之短信服务-Sikiro.SMS.Job服务的实现
- iota
- Java的IO流——(七)
- 梯度下降与pytorch
- 关于如何食用Xcode——用mac的小蒟蒻
- 并发编程—— FutureTask 源码分析