POJ2891Strange Way to Express Integers (线性同余方程组)
Choose k different positive integers a1, a2, …, ak. For some non-negative m, divide it by every ai (1 ≤ i ≤ k) to find the remainder ri. If a1, a2, …, ak are properly chosen, m can be determined, then the pairs (ai, ri) can be used to express m.
“It is easy to calculate the pairs from m, ” said Elina. “But how can I find m from the pairs?”
Since Elina is new to programming, this problem is too difficult for her. Can you help her?
Input
The input contains multiple test cases. Each test cases consists of some lines.
- Line 1: Contains the integer k.
- Lines 2 ~ k + 1: Each contains a pair of integers ai, ri (1 ≤ i ≤ k).
Output
Output the non-negative integer m on a separate line for each test case. If there are multiple possible values, output the smallest one. If there are no possible values, output -1.
Sample Input
2
8 7
11 9
Sample Output
31
Hint
All integers in the input and the output are non-negative and can be represented by 64-bit integral types.
线性同余方程组,终于自己写了一遍。棒棒哒。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#define ll long long
using namespace std;
void Ex_gcd(ll a,ll b,ll &d,ll &x,ll &y)
{
if(b==){ d=a; x=; y=; return ;}
Ex_gcd(b,a%b,d,y,x); y-=a/b*x;
}
int main()
{
ll c1,c2,c,a,b,d,x,y,n;
while(~scanf("%lld",&n)){
bool Flag=false;
scanf("%lld%lld",&a,&c1);
for(int i=;i<=n;i++) {
scanf("%lld%lld",&b,&c2);
if(Flag) continue; c=c2-c1;
Ex_gcd(a,b,d,x,y);
if(c%d!=) { printf("-1\n"); Flag=true;}
x=((c/d*x)%(b/d)+b/d)%(b/d);//最小正单元
c1=a*x+c1;a=a*b/d;
}
if(!Flag) printf("%lld\n",c1);
} return ;
}
最新文章
- iOS 自定义选项卡-CYLTabBarController
- Java为什么能跨平台运行
- jquery fadeOut 异步
- android之TabHost(下)
- 在C#中保存Bouncy Castle生成的密钥对
- Project Euler 76:Counting summations
- 浅谈Spring(二)
- thinkphp框架的大D方法应用
- 一个spring mvc 需要用到到文件
- CFtpFileFind例子
- JavaScript-手机中访问页面判断
- SpringMVC由浅入深day01_9商品修改功能开发
- JavaScript学习总结(十一)——Object类详解
- Java面向对象编程:封装,继承,多态
- python2.0_s12_day10_Twsited异步网络框架
- C#中Cookies的读取
- C#创建类,方法,接口,字段 的 默认类型
- HDU 5014 异或之和
- marquee标记
- commons-lang3-StringUtils
热门文章
- python pymysql安装
- Lumen开发:lumen源码解读之初始化(3)——单例(singleton)与中间件(Middleware)
- centos set up samba
- 九度OJ 1334:占座位 (模拟)
- 我的Android进阶之旅------>Android疯狂连连看游戏的实现之游戏效果预览(一)
- 12.Django数据库操作(执行原生SQL)
- PostgreSQL 里面的 BIGSERIAL
- [原创]Scala学习:关于变量(val,var,类型推断)
- 【二】MongoDB入门
- 【Flask】Sqlalchemy 常用数据类型