poj2891 中国剩余定理不互质

2024-02-19 14:08

本文主要是介绍poj2891 中国剩余定理不互质,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Elina is reading a book written by Rujia Liu, which introduces a strange way to express non-negative integers. The way is described as following:

 

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 (airi) can be used to express m.

“It is easy to calculate the pairs from m, ” said Elina. “But how can I find mfrom 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 airi (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.

题意:

     一个数m除以ai为bi,求这个数。

分析:

      裸的中国剩余定理,直接套的模板。

代码:

  

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include <iomanip>
#include<list>
#include<queue>
#include<sstream>
#include<stack>
#include<string>
#include<set>
#include<vector>
using namespace std;
#define PI acos(-1.0)
#define EPS 1e-8
#define MOD 1e9+7
#define LL long long
#define ULL unsigned long long     //1844674407370955161
#define INT_INF 0x7f7f7f7f      //2139062143
#define LL_INF 0x7f7f7f7f7f7f7f7f //9187201950435737471
const int dr[]={0, 0, -1, 1, -1, -1, 1, 1};
const int dc[]={-1, 1, 0, 0, -1, 1, -1, 1};
// ios.sync_with_stdio(false);
// 那么cin, 就不能跟C的scanf,sscanf,getchar,fgets之类的一起使用了。
LL ext_gcd(LL a,LL b,LL &x,LL &y)//扩展欧几里得算法
{if(!b){x=1,y=0;return a;}LL gcd=ext_gcd(b,a%b,y,x);//与下面的形式一样y=y-a/b*x;//注意这里/*LL gcd=ext_gcd(b,a%b,x,y);LL temp=x-a/b*y;x=y;y=temp;*/return gcd;
}
//逐一合并大法
LL CRT(LL w[],LL b[],LL k)//w为除数,b为余数,k为有多少式子
{LL Wi=w[0],ret=b[0];for(int i=1;i<k;++i){LL wi=w[i];LL bi=b[i];LL x,y;LL gcd=ext_gcd(Wi,wi,x,y);LL c=bi-ret;if(c%gcd)//表示没有结果return -1;LL W=wi/gcd;ret+=Wi*(((c/gcd*x)%W+W)%W);Wi*=W;}if(!ret)//表示余数全部为零{ret=1;for(int i=0;i<k;++i)ret=ret*w[i]/__gcd(ret,(LL)w[i]);//使用库函数求最小公倍数}return ret;
}
int main()
{LL w[100000],b[100000];int n;while(scanf("%d",&n)!=EOF){for(int i=0;i<n;++i){scanf("%lld%lld",&w[i],&b[i]);//除数}LL ans=CRT(w,b,n);printf("%lld\n",ans);}return 0;
}

 

这篇关于poj2891 中国剩余定理不互质的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/724899

相关文章

跨国公司撤出在华研发中心的启示:中国IT产业的挑战与机遇

近日,IBM中国宣布撤出在华的两大研发中心,这一决定在IT行业引发了广泛的讨论和关注。跨国公司在华研发中心的撤出,不仅对众多IT从业者的职业发展带来了直接的冲击,也引发了人们对全球化背景下中国IT产业竞争力和未来发展方向的深思。面对这一突如其来的变化,我们应如何看待跨国公司的决策?中国IT人才又该如何应对?中国IT产业将何去何从?本文将围绕这些问题展开探讨。 跨国公司撤出的背景与

uva 1342 欧拉定理(计算几何模板)

题意: 给几个点,把这几个点用直线连起来,求这些直线把平面分成了几个。 解析: 欧拉定理: 顶点数 + 面数 - 边数= 2。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc

从戴尔公司中国大饭店DTF大会,看科技外企如何在中国市场发展

【科技明说 | 科技热点关注】 2024戴尔科技峰会在8月如期举行,虽然因事未能抵达现场参加,我只是观看了网上在线直播,也未能采访到DTF现场重要与会者,但是通过数十年对戴尔的跟踪与观察,我觉得2024戴尔科技峰会给业界传递了6大重要信号。不妨简单聊聊:从戴尔公司中国大饭店DTF大会,看科技外企如何在中国市场发展? 1)退出中国的谣言不攻自破。 之前有不良媒体宣扬戴尔将退出中国的谣言,随着2

Java验证辛钦大数定理

本实验通过程序模拟采集大量的样本数据来验证辛钦大数定理。   实验环境: 本实验采用Java语言编程,开发环境为Eclipse,图像生成使用JFreeChart类。   一,验证辛钦大数定理 由辛钦大数定理描述为: 辛钦大数定理(弱大数定理)  设随机变量序列 X1, X2, … 相互独立,服从同一分布,具有数学期望E(Xi) = μ, i = 1, 2, …, 则对于任意正数ε ,

【中国国际航空-注册/登录安全分析报告】

前言 由于网站注册入口容易被黑客攻击,存在如下安全问题: 1. 暴力破解密码,造成用户信息泄露 2. 短信盗刷的安全问题,影响业务及导致用户投诉 3. 带来经济损失,尤其是后付费客户,风险巨大,造成亏损无底洞 所以大部分网站及App 都采取图形验证码或滑动验证码等交互解决方案, 但在机器学习能力提高的当下,连百度这样的大厂都遭受攻击导致点名批评, 图形验证及交互验证方式的安全性到底如

CPC23三 K.(Lucas定理)

K.喵喵的神·数 Time Limit: 1 Sec Memory Limit: 128 MB Description 喵喵对组合数比较感兴趣,并且对计算组合数非常在行。同时为了追求有后宫的素质的生活,喵喵每天都要研究质数。 我们先来复习一下什么叫做组合数。对于正整数P、T 然后我们再来复习一下什么叫质数。质数就是素数,如果说正整数N的约数只有1和它本身,N

中国书法——孙溟㠭浅析碑帖《越州石氏帖》

孙溟㠭浅析碑帖《越州石氏帖》 《越州石氏帖》  是一部汇集多本摹刻的帖,南宋时期的会稽石邦哲(字熙明)把家藏的一些法书碑帖集中一起摹刻成的,宋理宗时临安书商陈思《宝刻丛编》有记載这部帖的目录。现在还存有宋代时拓的残缺本,大多是相传的晋朝唐朝的小楷,后人多有临摹学习,并以此版本重新摹刻。 (图片来源于网络) 图文/氿波整理

将中国标准时间转换为年月日时分秒格式

1.将中国标准时间转换为年月日时分秒格式 代码如下(示例): // 时间格式化timestampToTime(timestamp) {var chinaStandard=Mon Jul 19 2021 11:11:55 GMT+0800 (中国标准时间);var date = new Date(chinaStandard);var y = date.getFullYear();var m =

热烈庆祝中国科学技术大学建校六六周年

卡西莫多的诗文集2022-2024.9月6-校庆国庆专版   欢迎分享 通过网盘分享的文件:卡西莫多的诗文集2022-2024.9月6-A5-校庆国庆专版.pdf 链接:  百度网盘 请输入提取码 提取码: umpm

《中国全屋智能行业发展现状与投资前景研究分析报告》

报告导读:本报告从国际全屋智能发展、国内全屋智能政策环境及发展、研发动态、供需情况、重点生产企业、存在的问题及对策等多方面多角度阐述了全屋智能市场的发展,并在此基础上对全屋智能的发展前景做出了科学的预测,最后对全屋智能投资潜力进行了分析。  订购链接:https://www.yxresearch.com/ 第一章全屋智能行业概念界定及发展环境剖析 第一节全屋智能行业相关概念界定 一、智能家