KIDx 的解题报告
该专题必备知识:解模线性方程
http://972169909-qq-com.iteye.com/blog/1104538
以下原创
转载请指明作者 (KIDx) 以及 文章地址:
http://972169909-qq-com.iteye.com/blog/1266328
问题描述:给出bi,ni的值,且n1, n2, n3,…, ni两两之间不一定互质,求Res的值?
解:采用的是合并方程的做法。
这里将以合并第一第二个方程为例进行说明
由上图前2个方程得(设k1、k2为某一整数):
例题: hdu 1573 X问题 【下面已给出代码】
http://acm.hdu.edu.cn/showproblem.php?pid=1573
另外推荐一题: hdu 3579 Hello Kiki:
http://acm.hdu.edu.cn/showproblem.php?pid=3579
#include <iostream>
using namespace std;
#define LL __int64
#define M 10
int N;
LL Egcd (LL a, LL b, LL &x, LL &y)
{
if (b == 0)
{
x = 1, y = 0;
return a;
}
LL d, tp;
d = Egcd (b, a%b, x, y);
tp = x;
x = y;
y = tp - a/b*y;
return d;
}
LL CRT2 (LL b[], LL n[], int num)
{
int i;
bool flag = false;
LL n1 = n[0], n2, b1 = b[0], b2, bb, d, t, k, x, y;
for (i = 1; i < num; i++)
{
n2 = n[i], b2 = b[i];
bb = b2 - b1;
d = Egcd (n1, n2, x, y);
if (bb % d) //模线性解k1时发现无解
{
flag = true;
break;
}
k = bb / d * x; //相当于求上面所说的k1【模线性方程】
t = n2 / d;
if (t < 0) t = -t;
k = (k % t + t) % t; //相当于求上面的K`
b1 = b1 + n1*k;
n1 = n1 / d * n2;
}
if (flag)
return 0; //无解
/******************求正整数解******************/
if (b1 == 0) //如果解为0,而题目要正整数解,显然不行
b1 = n1; //n1刚好为所有ni的最小公倍数,就是解了
/******************求正整数解******************/
if (b1 > N)
return 0;
return (N-b1)/n1+1; //形成的解:b1, b1+n1, b1+2n1,..., b1+xni...
}
int main()
{
int t, num, i, cc = 1;
LL b[M], n[M];
scanf ("%d", &t);
while (t--)
{
scanf ("%d%d", &N, &num);
for (i = 0; i < num; i++)
scanf ("%I64d", n+i);
for (i = 0; i < num; i++)
scanf ("%I64d", b+i);
printf ("%I64d\n", CRT2 (b, n, num));
}
return 0;
}
- 大小: 1.9 KB
- 大小: 18.1 KB
- 大小: 20.3 KB
- 大小: 50.9 KB
分享到:
相关推荐
算法-分成互质组 (信息学奥赛一本通-T1221)(包含源程序).rar
中国剩余定理(不互质的情况) 对互质的情况,处理起来比较方便,可以直接套模板 本题给出不互质的模线性方程组,求出满足方程的最小正整数解 方案:对于不互质的模线性方程组,可以进行方程组合并,求出合并后的方程...
中国剩余定理Matlab代码使用中国余数定理将两个大数相加 问题陈述 问题编号27-编写MATLAB代码以使用中文余数定理添加超过计算机字大小的大整数。 团队成员 塔伦·阿南德(Tarun Anand)-16CO147 阿奇特·潘迪-16CO...
均匀直线,互质阵列,嵌套阵列可修改参数(频率,阵元个数,阵元间距)
线性同余方程(组) 中国剩余定理 扩展中国剩余定理 3. 高斯消元 4. 组合计数 加法原理和乘法原理 排列数和组合数 组合数的性质 二项式定理 5. 简单容斥原理 各集合的交集 容斥原理 6. 概率与数学期望...
本文实例讲述了Python实现的中国剩余定理算法。分享给大家供大家参考,具体如下: 中国剩余定理(Chinese Remainder Theorem-CRT):又称孙子定理,是数论中的一个定理。即如果一个人知道了一个数n被多个整数相除得到...
论文研究-互质因子摄动系统的敏感性分析.pdf,
基于降阶(非最小阶)观测器的设计,明确给出了一种新的线性时不变系统双互质分解的状态空间表示,并相应得到了真镇定控制器参数化结果的状态空间解释.与以往的结果相比...
中国剩余定理(CRT)解法 程序的缺点:未对输入的模进行互质校验!有时间请大家可以把input函数中加入互质校验。
一种基于互质采样的相关检测算法,曹斌,赵成林,在信号的相关检测应用中,随着被检测信号频率和带宽的增加,要求采样频率大幅增大,需要处理的数据量也随之增大,造成了实际系统
电信设备-基于周期互质混合编码的目标物体三维信息获取方法.zip
一、模运算 二、最大公约数 三、欧拉定理 四、模线性方程 五、中国余数定理 六、模数不互质的同余方程组 七、A^B mod C 八、素数
1、互质面阵模型建立。 2、主要实现了 二维MUSIC估计算法下,互质面阵的模糊解决算法。 【代码特点】:参数化编程(参数可方便修改)、思路步骤清晰、注释明细。 【适合对象】:信号处理、雷达专业学生。 【乱码问题...
《数学女孩2:费马大定理》中每一章针对不同议题进行解说,非常适合对数学感兴趣的初高中生以及成人阅读。 Contents: Chapter 1. 将无限宇宙尽收掌心 Chapter 2. 勾股定理 Chapter 3. 互质 Chapter 4. 反证法 ...
1.版本:matlab2019a,不会运行可私信 2.领域:基础教程 3.内容:Matlab实现基于互质阵的DOA估计 4.适合人群:本科,硕士等教研学习使用
资源名:互质阵列中稀疏表示理论完成DOA估计算法_matlab 资源类型:matlab项目全套源码 源码说明: 全部项目源码都是经过测试校正后百分百成功运行的,如果您下载后不能运行可联系我进行指导或者更换。 适合人群:...