再说中国剩余定理、扩展欧几里德和同余方程组

2024-08-28 00:48

本文主要是介绍再说中国剩余定理、扩展欧几里德和同余方程组,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

E - 解同余线性方程组1
Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u
Submit  Status

Description

Andy和Mary养了很多猪。他们想要给猪安家。但是Andy没有足够的猪圈,很多猪只能够在一个猪圈安家。举个例子,假如有16头猪,Andy建了3个猪圈,为了保证公平,剩下1头猪就没有地方安家了。Mary生气了,骂Andy没有脑子,并让他重新建立猪圈。这回Andy建造了5个猪圈,但是仍然有1头猪没有地方去,然后Andy又建造了7个猪圈,但是还有2头没有地方去。Andy都快疯了。你对这个事情感兴趣起来,你想通过Andy建造猪圈的过程,知道Andy家至少养了多少头猪。

Input

输入包含多组测试数据。每组数据第一行包含一个整数n (n <= 10) – Andy建立猪圈的次数,解下来n行,每行两个整数ai, bi( bi <= ai <= 1000), 表示Andy建立了ai个猪圈,有bi头猪没有去处。你可以假定(ai, aj) = 1.

Output

输出包含一个正整数,即为Andy家至少养猪的数目。

Sample Input

3
3 1
5 1
7 2

Sample Output

16



在上篇博客中已经说了用中国剩余定理求同余方程组,这次又有所收获,故再详谈之。

在开始说中国剩余定理之前,再谈谈欧几里德算法和扩展欧几里德算法:

首先,欧几里德算法就是用递归的方式算两个数的最大公约数,其依据就是定理:gcd(a,b)=gcd(b,a mod b) (a>b 且 a mod b不为0)
代码就很容易了:
int gcd(int a,int b)  
{  
if(b==0)return a;  
else return gcd(b,a%b);  
}

再次,就是扩展欧几里德算法,先看内容:
对于不完全为 0 的非负整数 a,b,gcd(a,b)表示 a,b 的最大公约数,必然存在整数对 x,y ,使得 gcd(a,b)=ax+by。
它也是用递归的方式实现,为什么用递归的呢??这是由它的推导过程决定的:
求解 x,y的方法的理解
设 a>b。
1,显然当 b=0,gcd(a,b)=a。此时 x=1,y=0;
2,ab<>0 时
设 ax1+by1=gcd(a,b);
bx2+(a mod b)y2=gcd(b,a mod b);
根据朴素的欧几里德原理有 gcd(a,b)=gcd(b,a mod b);
则:ax1+by1=bx2+(a mod b)y2;
即:ax1+by1=bx2+(a-[a/b]*b)y2=ay2+bx2-[a/b]*by2;
也就是ax1+by1==ay2+b(x2-[a/b]*y2);
根据恒等定理得:x1=y2; y1=x2-[a/b]*y2;
这样我们就得到了求解 x1,y1 的方法:x1,y1 的值基于 x2,y2.
因为 gcd 不断的递归求解一定会有个时候 b=0,所以递归可以结束(return a)。

再看代码:

int Egcd(int a,int b,int& x,int& y)
{
int d,t;
if(!b)
{
x=1;y=0;return a;
}
else
{
Egcd(b,a%b,y,x);
y-=x*(a/b);
}
}

该函数有4个参数,分别对应着 gcd(a,b)=ax+by,其中并没有关于gcd(a,b)的参数传进去(其实求出的结果是和gcd(a,b)无关的,所以无需传它的参数)
我们分别设这个4个参数为:   a:①,b:②,x:③,y:④  (注意,x,y传入的是地址,因为结果要放在x,y里)
故方程的形式:①*③+②*④=k(常数),故要想求③,把①、②、③、④按顺序放入Egcd的函数的参数中即可,便可得③。
欧几里德就说完了,接下来就是要说中国剩余定理了。

中国剩余定理简单来说就是:a = ai(mod ni),求未知数a。

设 n=n1*n2...nk, 其中因子两两互质.有:  a-----(a1,a2,...,ak), 其中ai = a mod ni, 则 a和(a1,a2,...,ak)关系是一一对应的.就是说可以由 a求出(a1,a2,...,ak), 也可以由(a1,a2,...,ak)求出a
下面说说由(a1, a2, ..., ak)求a的方法:
定义 mi = n1*n2*...nk / ni;   ci = mi*(mf  mod ni);(在这里,很多地方写的没有那个*号,我在这加上,大家就很明了了)   其中 mi*mf  mod ni = 1;
         则 a = (a1*c1+a2*c2+...+ak*ck)      (mod n)      (注:由此等式可求a%n, 当n很大时)
a = (a1*c1+a2*c2+...+ak*ck)      (mod n)可知,a是由ai和ci对应相乘再相加等到的,其中在题中ai应为余数(已知),ni为除数(已知),而ci是需要算的,且ci = mi*(mf mod ni),还有 mi = n1*n2*...nk / ni(已知),所以只需且关键求出mf!!mf怎么求,别闹,上边扩展欧几里德讲了那么多,可不是白说的,来,看!

mf求法:如果理解了扩展欧几里得 ax+by=d, 就可以想到:
                     mi*mf  mod ni = 1 => mi*mf+ni*y=1;

对于这个式子 mi*mf+ni*y=1应该很熟悉吧,没错,就是用Egcd来求mf!

①:mi,②:ni,③:mf,④:y,不是想要mf吗?!把它放到③吧!

接下来就很简单了吧,看代码:

		for(i=0;i<n;i++)
s*=a[i];
for(i=0;i<n;i++)
{
m=s/a[i];			//m表示mi
gcd(m,a[i],x,y);
x=(x%a[i]+a[i])%a[i];
sum=(sum+m*b[i]*x%s)%s;			//这里换做用bi表示余数
		}

好了,说完了,下面是该题的全部代码:

#include <stdio.h>
#include <string.h>
#include <math.h>
typedef __int64 int64;				//这里要用64位
int64 a[11],b[11];
int64 Egcd(int64 a,int64 b,int64& x,int64& y)
{
int64 d,t;
if(!b)
{
x=1;y=0;return a;
}
else
{
Egcd(b,a%b,y,x);
y-=x*(a/b);
}
}
int main()
{
int64 sum,m,s,x,y;
int n,i;
while(scanf("%d",&n)!=EOF)
{
sum=0;s=1;
for(i=0;i<n;i++)
scanf("%I64d %I64d",&a[i],&b[i]);
for(i=0;i<n;i++)
s*=a[i];
for(i=0;i<n;i++)
{
m=s/a[i];
Egcd(m,a[i],x,y);
x=(x%a[i]+a[i])%a[i];
sum=(sum+m*b[i]*x%s)%s;
}
printf("%I64d\n",sum);					//既然要用64位,那输入输出也要用%I64d,否则用%d提交也会WA的。。。。
}
return 0;
}

这里把代码中的int 改成了int64,主要是为了保证一些比较大的数能够过。

这篇关于再说中国剩余定理、扩展欧几里德和同余方程组的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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

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

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

科研绘图系列:R语言扩展物种堆积图(Extended Stacked Barplot)

介绍 R语言的扩展物种堆积图是一种数据可视化工具,它不仅展示了物种的堆积结果,还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异,为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl

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

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

Spring框架5 - 容器的扩展功能 (ApplicationContext)

private static ApplicationContext applicationContext;static {applicationContext = new ClassPathXmlApplicationContext("bean.xml");} BeanFactory的功能扩展类ApplicationContext进行深度的分析。ApplicationConext与 BeanF

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

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

PHP7扩展开发之数组处理

前言 这次,我们将演示如何在PHP扩展中如何对数组进行处理。要实现的PHP代码如下: <?phpfunction array_concat ($arr, $prefix) {foreach($arr as $key => $val) {if (isset($prefix[$key]) && is_string($val) && is_string($prefix[$key])) {$arr[

PHP7扩展开发之字符串处理

前言 这次,我们来看看字符串在PHP扩展里面如何处理。 示例代码如下: <?phpfunction str_concat($prefix, $string) {$len = strlen($prefix);$substr = substr($string, 0, $len);if ($substr != $prefix) {return $prefix." ".$string;} else

PHP7扩展开发之类型处理

前言 这次,我们将演示如何在PHP扩展中如何对类型进行一些操作。如,判断变量类型。要实现的PHP代码如下: <?phpfunction get_size ($value) {if (is_string($value)) {return "string size is ". strlen($value);} else if (is_array($value)) {return "array si

PHP7扩展开发之依赖其他扩展

前言 有的时候,我们的扩展要依赖其他扩展。比如,我们PHP的mysqli扩展就依赖mysqlnd扩展。这中情况下,我们怎么使用其他扩展呢?这个就是本文讲述的内容。 我们新建立一个扩展,名字叫 demo_dep , 依赖之前的say扩展。 在demo_dep扩展中,我们实现demo_say方法。这个方法调用say扩展的say方法。 代码 基础代码 确保say扩展的头文件正确安装到了php