精华内容
下载资源
问答
  • 中国剩余定理C++实现

    千次阅读 2020-09-07 01:36:32
    中国剩余定理C++实现 笔者最近对中国剩余定理产生兴趣,遂以C++写为代码,在此记录一下。 中国剩余定理 中国剩余定理源于《孙子算经》,其具体在于解决以下形式方程: 核心公式为: C++代码实现 要实现以上...

    中国剩余定理C++实现

    笔者最近对中国剩余定理产生兴趣,遂以C++写为代码,在此记录一下。

    1、中国剩余定理

    中国剩余定理源于《孙子算经》,其具体在于解决以下形式方程:
    在这里插入图片描述

    核心公式为:
    在这里插入图片描述

    2、C++代码实现

    要实现以上公式 ,需要两部分,一是算出公式中乘法逆元部分,二是完成公式主体部分计算。
    乘法逆元部分使用扩展欧几里得算法,代码如下:

    int ex_gcd(int a, int b, int &x, int &y)       //扩展欧几里得 
    {
    	if (!b)
    	{
    		x = 1;
    		y = 0;
    		return a;
    	}
    	int r = ex_gcd(b, a%b, x, y);
    	int t = x;
    	x = y;
    	y = t - a / b * y;
    	return r;
    }
    
    int mod_reverse(int a, int n)//ax=1(mod n) 求a的逆元x 
    {
    	int d, x, y;
    	d = ex_gcd(a, n, x, y);
    	if (d == 1)
    		return (x%n + n) % n;
    	else
    		return -1;
    }
    
    

    公式主体部分:其中输入以CH_Remainder结构体储存,格式为{2,3}(模3余2)

    typedef struct CH_Remainder
    {
    	int result, mod_num;
    }CH_Remainder,ch_remainder[100];
    
    int Ch_remainder_theorem(ch_remainder a )//主体部分
    {
    	int k=a[0].mod_num;
    	int b = 0, z = 0;
    	for (int i = 1; a[i].mod_num; i++)
    	{
    		k *= a[i].mod_num;
    	}
    	for (int i = 0; a[i].mod_num; i++)
    	{
    		z = mod_reverse(k / a[i].mod_num, a[i].mod_num);//乘法逆元
    		if (z==-1) return -1;
    		b += (a[i].result*(k / a[i].mod_num)*z);
    	}
    	return b % k;
    }
    
    

    3、具体使用
    以经典的“物不知数”问题为例,其正文为:有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?
    主函数调用如下:

    int main()
    {
    	ch_remainder a = { {2,3},{3,5},{2,7} };
    	cout <<Ch_remainder_theorem(a) << endl;
    }
    

    结果为:
    在这里插入图片描述

    展开全文
  • 密码学实验二之中国剩余定理C++实现。我的作业。希望对大家有帮助。适合于密码学和c++初学者。
  • C++ 求解中国剩余定理的实现 采用辗转相除法,使用了std vector
  • C++实现中国剩余定理

    2021-06-13 09:00:25
    这是一种非常简单的思想,没有用到中国剩余定理中的公式; 函数中k为最终结果,s为前i个数的最小公倍数 具体步骤见代码注释 Code #include<iostream> #include<algorithm> using namespace std; int a...

    这是一种非常简单的思想,没有用到中国剩余定理中的公式;
    函数中k为最终结果,s为前i个数的最小公倍数
    具体步骤见代码注释

    Code

    #include<iostream>
    #include<algorithm>
    using namespace std;
    int a[15],p[15],n;
    int crt(int a[],int p[],int n){
    	int k=p[1],s=a[1];//k初值为第一个数的余数这是满足第一个数余数条件的最小值,s当前为前1个数的最小值
    	for(int i=2;i<=n;i++){
    		while(k%a[i]!=p[i]) k+=s;//只要k不符合下一个条件,疯狂累加最小公倍数
    		s*=a[i];//s累乘,最小公倍数范围增加1
    	}
    	return k;
    }
    int main(){
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++){
    		scanf("%d%d",&a[i],&p[i]);
    	}
    	printf("%d",crt(a,p,n));
    	return 0;
    }
    
    展开全文
  • 中国剩余定理c++

    千次阅读 2019-04-09 21:04:58
    一个正整数K,给出K Mod 一些质数的结果,求符合条件的最小的K。例如,K % 2 = 1, K % 3 = 2, K % 5 = 3。符合条件的最小的K = 23。 收起 输入 第1行:1个数N表示后面输入的质数及模的数量。(2 <...

    一个正整数K,给出K Mod 一些质数的结果,求符合条件的最小的K。例如,K % 2 = 1, K % 3 = 2, K % 5 = 3。符合条件的最小的K = 23。
    收起
    输入
    第1行:1个数N表示后面输入的质数及模的数量。(2 <= N <= 10)
    第2 - N + 1行,每行2个数P和M,中间用空格分隔,P是质数,M是K % P的结果。(2 <= P <= 100, 0 <= K < P)
    输出
    输出符合条件的最小的K。数据中所有K均小于10^9。
    输入样例
    3
    2 1
    3 2
    5 3
    输出样例
    23

    基本思想:先求出满足前两项的K的值,然后求出前两项的最小公倍数,将前两项最小公倍数作为K的新值,重复上述操作,求出满足前三个K的值,以此类推。

    #include<iostream>
    #include<algorithm>
    using namespace std;
    int a[15],p[15];
    int main()
    {
    	int n;
    	cin>>n;
    	for(int i=0;i<n;i++)
    	{
    		cin>>a[i]>>p[i];
    	}
    	int k=p[0],s=1;
    	for(int i=0;i<n-1;i++)
    	{
    		s=s*a[i];//s为a[i]前i项的最大公倍数,并且所有整数之间互质 
    		while(k%a[i+1]!=p[i+1])
    		  k+=s;//当目前K不满足条件是,加上前i项的最大公倍数 
    	}
    	cout<<k<<endl;
    	return 0;
    }
    
    展开全文
  • 题目 给定2n 个整数 a1,a2,…,an和 m1,m2,…,mn,求一个最小的非负整数x,满足∀i∈[1,n],x≡mi(modai)。 输入格式 第1行包含整数n。 第2…n+1 行:每i+1行包含两个整数ai和mi,数之间用空格隔开。...

    题目

    给定 2n 个整数 a1,a2,…,an 和 m1,m2,…,mn,求一个最小的非负整数 x,满足 ∀i∈[1,n],x≡mi(mod ai)。

    输入格式

    第 1 行包含整数 n。

    第 2…n+1 行:每 i+1 行包含两个整数 ai 和 mi,数之间用空格隔开。

    输出格式

    输出最小非负整数 x,如果 x 不存在,则输出 −1。
    如果存在 x,则数据保证 x 一定在 64 位整数范围内。

    数据范围

    1≤ai≤231−1,
    0≤mi<ai
    1≤n≤25

    输入样例:

    2
    8 7
    11 9
    

    输出样例:

    31

    思路

    代码

    #include<iostream>
    
    using namespace std;
    
    typedef long long LL;
    
    LL exgcd(LL a, LL b, LL &x, LL &y)
    {
    	if(!b)
    	{
    		x = 1, y = 0;
    		return a;
    	}
    	
    	LL d = exgcd(b, a % b, y, x);
    	y -= a / b * x;
    	return d;
    }
    
    int main()
    {
    	int n;
    	cin >> n;
    	
    	bool flag = true;
    	
    	LL a1, m1;
    	cin >> a1 >> m1;
    	
    	for(int i = 0; i < n - 1; i ++)//合并等式 
    	{
    		LL a2, m2;
    		cin >> a2 >> m2;
    		
    		LL k1, k2;
    		LL d = exgcd(a1, a2, k1, k2);
    		
    		if((m2 - m1) % d)
    		{
    			flag = false;
    			break;
    		}
    		
    		k1 *= (m2 - m1) / d;
    		LL t = a2 / d;
    		k1 = (k1 % t + t) % t;
    		
    		m1 = a1 * k1 + m1;
    		a1 = abs(a1 / d * a2);
    	}
    	
    	if(flag)
    		cout << (m1 % a1 + a1) % a1 << endl;
    	else puts("-1");
    	
    	return 0;
    }

     

    展开全文
  • 中国剩余定理cpp代码

    2017-12-30 20:03:00
    #include #include using namespace std; typedef int LL; typedef pair, LL> PLL; LL inv(LL t, LL p) {//求t关于p的逆元 if (t >= p) ... 1 : (p - p / t) * inv(p % t, p) % p;...PLL linear(LL A[], LL B[], LL M[]...
  • #include<iostream> #include<algorithm> #include<cmath> using namespace std; typedef long long LL; const int N=100; LL k=4,n=7,s_start=67187511; //m1=97,m2=98,m3=99,...LL m[N],s[N],M_a
  • 中国剩余定理 cpp实现

    2011-05-06 10:19:17
    中国剩余定理 用。cpp实现 包含全部代码,并且已经调试成功! 对于学习安全方面的人有很大参考价值!
  • #include&lt;iostream&gt; #include&lt;stdio.h&gt; using namespace std;.../***********************...中国剩余定理 ai=x(mod mi) 求x eg:1=x(mod 11) 2=x(mod 7) 最后求得为满足条件的最小值 ***...
  • 通过C++实现中国剩余定理算法的实现。 二.试验原理 设正整数 m1,m2,...,mk 两两互素,对任意整数 a1,a2,...,ak,一次 同余方程组: 在模m意义下有唯一解,该解可表示为: 三.所用miracl函数 (1)...
  • "三个m并不两两互素,不能直接使用中国剩余定理\n" ) ; //结束 } else { multiply ( m1 , m2 , m ) ; multiply ( m , m3 , m ) ; //计算m=m1*m2*m3 fdiv ( m , m1 , Mi1 ) ; ...
  • 针对大数的中国剩余定理C实现
  • 经典例题 AcWing 204. 表达整数的奇怪方式 给定 2n 个整数a1,a2,…,an和m1,m2,…,mn,求一个最小的非负整数 x,满足∀i∈[1,n],x≡mi(mod ai)。 输入格式 第1 行包含整数 n。 第 2…n+1行:每 i+1 行包含两个整数ai...
  • https://ac.nowcoder.com/acm/contest/890/D 板子题套个好板子即可ac 1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll __int128 ... 5 void exgcd(ll a,ll b,ll &...
  • 中国剩余定理也称孙子定理,是中国古代求解一次同余式组(见同余)的方法。是数论中一个重要定理。 这玩意在luogu居然有模板题: [TJOI2009]猜数字 先来看一个问题: 在《孙子算经》中有这样一个问题:“今有物不知...
  • 中国剩余定理编程实现

    千次阅读 2017-02-16 14:55:30
    中国剩余定理 主要内容:  本文主要论述了中国剩余定理的背景,由来,证明方法,编程算法解决以及一些简单的应用,文章阐述了中国剩余定理的由来,介绍了他的几种解法.包括他的中国剩余定理研究,研究中国剩余...
  • 暴力枚举超时,用中国剩余定理解决。 方法就是除3的余数a乘上70,除5的余数b乘上21,除7的余数c乘上15,最后再取余105(3 * 5 * 7) 70,21,15实际上是一种巧妙的构造方法。 70是5和7的公倍数,且被3除余1 21...
  • 中国剩余定理(CRT): 若 m1, m2,...,mk 两两互质,则同余方程组 x≡a1 (mod m1) x≡a2 (mod m2) ………………… x≡ak (mod mk) 有整数解,解为 其中: long long CRT(long long a[], long long m[]...
  • 可以看到两者中国剩余定理pro的适用范围更广,所以我推荐使用中国剩余定理pro,中国剩余定理可以了解一下。 如果你还不知道下面的知识,请自行百度补习: 1.拓展欧几里得算法求解如下不定方程及如何拓展到求此不定...
  • 中国剩余定理.cpp

    2020-07-14 14:22:33
    利用C++编写的用来计算中国剩余定理的代码,内含详细注释,每一步的结果都有展示,方便快捷,为学习信息安全数学基础的同学带来了福音。
  • 扩展中国剩余定理

    2019-08-23 20:47:44
    先简单介绍下线性同余方程 ax%n=b 其有解需满足(a,n)|b,令d=gcd(a,n) 设t为(a/d)x % (n/d) = (b/d)的唯一解,则ax%n=b的d个解为t,t+...=n,r[i],a[i]均为正整数),判断是否存在最小非负整数解,为一般方程不考虑中国...
  • 中国剩余定理(西方数学史中的叫法),就是上一题目的一般情况。 设m1,m2...mk是两两互素的正整数,即: gcd(mi, mj) = 1 (其中 i != j, i, j >= 1且 ). 则同余方程组: x  ≡ a1(mod m1) x  ≡ a2(mod m2...
  • 题目描述 学校要进行合唱比赛了,于是班主任小刘准备给大家排个队形。 他首先尝试排成 m1 行,发现最后多出来 a1 个同学;接着他尝试排成 m2 行,发现最后多出来 a2 个同学,……,他们尝试了 n 种排队方案,但...
  • 中国剩余定理 用来求解同余方程组的最小非负整数解,其中都互质 首先让 M 等于所有的最小公倍数,对于求解每一个的方程 先设一个,再求解其逆元 则会有一组最小解 其通解就是 如果没有看懂,可以看详细...
  • 中国剩余定理的C语言实现(基于Miracl大数运算库)

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,559
精华内容 1,023
关键字:

中国剩余定理c++

c++ 订阅